1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Finding cycles in a graph

  1. Feb 15, 2016 #1
    1. The problem statement, all variables and given/known data

    2. Relevant equations
    Recursion, graphs, DFS
    3. The attempt at a solution
    To try to solve this algorithm, I first need to find all the basic cycles in the Graph G. When I have these cycles, I can simply pick the smallest edge in each of them and add them to the set F, while removing duplicates, which is trivial. However, I can't figure out an algorithm that would give me all the cycles in polynomial time.

    I tried using a modified Depth First Search recursive method that, when it reaches a node that has already been visited, backtracks until it reaches again to find the cycle. However, for a simple graph with 8 nodes and 14 links my method gets called more than 500 times... I tried using what is described here: http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph/549312#549312

    Am I thinking about this problem correctly? What approach other than finding the cycles could I use? Thanks
  2. jcsd
  3. Feb 15, 2016 #2
    Could I simply use Boruvka's algorithm to get a minimum spanning tree and add these edges to F?
  4. Feb 16, 2016 #3
    I think all the edges that are not in a maximum spanning tree wil give me the minimum hitting set.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted