Timeline for Complexity of determining if two graphs have same cycle matroid?
Current License: CC BY-SA 2.5
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 6, 2009 at 0:01 | vote | accept | Gordon Royle | ||
| Nov 9, 2009 at 7:23 | |||||
| Nov 5, 2009 at 4:17 | history | edited | David E Speyer | CC BY-SA 2.5 |
added 203 characters in body
|
| Nov 5, 2009 at 4:04 | comment | added | David E Speyer | Uggh, so you really do want to think about that issue. Well, if Cunningham/Edmonds doesn't turn out to make it clear, you might also want to check "Structure and enumeration of two-connected graphs with prescribed three-connected components " ams.org/mathscinet-getitem?mr=2524178 , by Gagarin, Labelle, Leroux, and Walsh. | |
| Nov 5, 2009 at 3:54 | history | edited | David E Speyer | CC BY-SA 2.5 |
deleted 2 characters in body; deleted 23 characters in body
|
| Nov 5, 2009 at 3:48 | comment | added | Gordon Royle | Yes, it seems like it SHOULD be the same as graph isomorphism and your answer gives a more detailed rationale for that. My only concern is whether one could find some graph with lots of nested 2-cuts that you couldn't untangle, but perhaps Cunningham/Edmonds is the place to check that this cannot occur. Overall it seems like somebody (else) should have done this already and published it! | |
| Nov 5, 2009 at 3:43 | vote | accept | Gordon Royle | ||
| Nov 6, 2009 at 0:01 | |||||
| Nov 5, 2009 at 3:31 | history | edited | David E Speyer | CC BY-SA 2.5 |
added 71 characters in body
|
| Nov 5, 2009 at 2:55 | history | answered | David E Speyer | CC BY-SA 2.5 |