search
Log In
1 vote
142 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 142 views

1 Answer

1 vote
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

Related questions

1 vote
1 answer
1
169 views
Your team is playing a chess tournament against a visiting team. Your opponents have arrived with a team of M players, numbered $1, 2, \dots , M$. You have $N$ players, numbered $1, 2, \dots , N$ from which to choose your team, where $N \geq M$. Each of the $M$ ... Propose an efficient algorithm to solve this problem and analyse its complexity.
asked May 19, 2016 in Algorithms jothee 169 views
1 vote
1 answer
2
154 views
A finite sequence of bits is represented as a list with values from the set $\{0,1\}$-for example, $[0,1,0], [1,0,1,1], \dots [ \: ]$ denotes the empty list, and $[b]$ is the list consisting of one bit $b$. For a nonempty list $l, \text{ head}(l)$ returns the first element of ... bit. g2(n) if (n == 0) then return(0) else return f2(g2(n-1),g1(n)) endif What is the value of $g2(256)$ and $g2(257)$?
asked May 27, 2016 in Algorithms jothee 154 views
1 vote
1 answer
3
170 views
Consider a plate stacked with several disks, each of a different diameter (they could all be, for instance, $\text{dosas}$ or $\text{chapatis}$ of different sizes). We want to sort these disks in decreasing order according to their diameter so that the widest disk is ... or $\text{chapatis}$ between two big spoons and flipping the stack.) How many steps will your algorithm take in the worst case?
asked May 27, 2016 in Algorithms jothee 170 views
12 votes
3 answers
4
760 views
Consider a plate stacked with several disks, each of a different diameter (they could all be, for instance, $\text{dosas}$ or $\text{chapatis}$ of different sizes). We want to sort these disks in decreasing order according to their diameter so that the widest ... $\text{chapatis}$ between two big spoons and flipping the stack.) Give an algorithm for sorting the disks using this operation.
asked May 19, 2016 in Algorithms jothee 760 views
...