The Gateway to Computer Science Excellence
+1 vote
84 views
Let $G=(V,E)$ be a undirected graph. We say $S \subseteq V$ is a clique if and only if for all $u,\: v \: \in S$, the edge $(u, v)$ is in $E$.

Now let $G=(V,E)$ be a graph in which each vertex has degree at most 5. Give an algorithm to find the largest clique in $G$. What is the complexity of your algorithm?
in Algorithms by Veteran (105k points) | 84 views

1 Answer

0 votes
Since the degree of each vertex is 5. So the largest clique cannot have more than 6 vertices.  So take all the subgraphs of the graph who has less than or equal to 6vertices and find the largest clique among them. Note that we can always find clique of size 3. So we have to check for the graphs having vertices >3 and <=6
by Loyal (9.8k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,321 answers
198,394 comments
105,144 users