babak's blog

Girth of Graph
By babak, 15 years ago, In English

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 :)

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

»
15 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
15 years ago, hide # |
 
Vote: I like it +48 Vote: I do not like it

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).

→ Reply