Блог пользователя babak

Girth of Graph
Автор babak, 12 лет назад, По-английски

Let G be a graph with n vertices and Δ(G)≤10 . find an algorithm with O(n) compolexity to determine this graph has girth less than 20 or not ?

thanks for any hint :)

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

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

what is less than or equal to 10? number of vertices? with n <= 10 we can just check all possible subsets.

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

The solution is as straightforward as it is practically useless. Let's use brute-force backtracking algorithm to find all paths of length no more than 20, and check if any of them is a cycle. It will do about n*10^20 operations, which is still O(n).

→ Ответить