Блог пользователя m.khooryani

Автор m.khooryani, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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.