m.khooryani's blog

print all complete sub graphs in graph
By m.khooryani, history, 9 years ago, In English

can some one help to solve the problem with good time complexity?

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

There isn't a polynomial time algorithm to find cliques in a graph, and their number can be an exponential function of the number of nodes. Your only choice is to use backtracking.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

This problem is related to the "The Clique Problem" and unfortunately it's NP complete, i.e no polynomial time algorithm has been found till now. Your options are, backtracking or Approximation algorithms.

→ Reply