Timeline for A graph connectivity problem (restated)
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 1, 2009 at 21:44 | vote | accept | Sheldoniz | ||
| Dec 1, 2009 at 6:03 | comment | added | Harrison Brown | It's even NP-complete with m = 1 and restricted to planar graphs, see portal.acm.org/citation.cfm?id=1598870. This also gives some classes of graphs for which there is a polynomial-time algorithm, though I suspect the constants can be huge (bounded tree-width?!). | |
| Dec 1, 2009 at 1:32 | history | answered | David Eppstein | CC BY-SA 2.5 |