babak's blog

Girth of Graph
By babak, 13 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

»
13 years ago, # |
← 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
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    I think Δ(G) means the maximum degree of vertices on G.

    → Reply
»
13 years ago, # |
  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