- #1
wololo
- 27
- 0
Homework Statement
Homework Equations
Recursion, graphs, DFS
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