K-Clique in Connected Graphs

StackOverflow https://stackoverflow.com/questions/13870887

Question

A question about the clique problem (specifically k-clique). Is there any algorithm that takes advantage of the properties of connected graphs to find cliques of a given size k, if such cliques exist?

Was it helpful?

Solution

Any algorithm can be made to take advantage of connected components. Just find the connected components before running the algorithm, discard those smaller than k and run the algorithm separately on each of the remaining ones.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top