Interview Question
AnalystsCountry: India
It's possible to check all combinations of 6 nodes for whether they are a clique. Then all combinations of 5, 4, 3, .... This is O(n^6). If we further knew that the graph was a connected graph, we'd know the max clique size is 5 (unless the graph has only 6 vertices) and be able to cut down the time to O(n^5).
finding the largest clique is np-complete
- ? May 14, 2012here we have that every vertex of degree at most 5, so maximal clique can be of size 6
though i am not sure how this can help us..