Timeline for Fundamental Cycles of a graphs
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 10, 2014 at 19:10 | history | edited | David Eppstein | CC BY-SA 3.0 |
added 411 characters in body
|
| Dec 16, 2013 at 20:03 | vote | accept | hbm | ||
| Dec 4, 2013 at 7:30 | comment | added | David Eppstein | Yes, a largest set, and they're all trees iff they all have exactly $n-1$ edges. | |
| Dec 4, 2013 at 6:11 | comment | added | Brendan McKay | I think you mean "a" largest set; but if one is a tree than they all are. Right? | |
| Dec 4, 2013 at 3:35 | comment | added | David Eppstein | The subsets of edges that do not include any cycles form the independent sets of a matroid. The subsets of edges that don't include all of the unique edges of some cycle form the independent sets of a different matroid. When you have two matroids on the same elements, you can find the largest set that's independent for both of them, in polynomial time. If this set is a tree, you've solved the problem, and if not there is no solution. | |
| Dec 4, 2013 at 1:40 | comment | added | hbm | I am sure I follow. Could you explain? | |
| Nov 29, 2013 at 0:16 | history | answered | David Eppstein | CC BY-SA 3.0 |