Timeline for Where is it shown how to construct a decomposition tree for a series-parallel graph in linear time?
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 23, 2010 at 3:13 | comment | added | David Eppstein | That sounds like it should work. Make sure to count an edge st (if it exists) as one of the components that you include in the parallel composition, though. | |
| Jul 23, 2010 at 0:17 | comment | added | Gordon Royle | Yes, I read your paper but couldn't quite figure out how to get the tree from the ear decomposition. Supposing we know the terminals in the final graph, is it possible to turn the following into a linear time algorithm (my analysis of algorithms skills are both limited and rusty). (1) If (G,s,t) has cut-vertices then it is a series-composition of a bunch of 2-connected pieces. Form node with these as children and recurse. (2) Otherwise if {s,t} is a 2-vertex cut then delete {s,t}, find the connected components G_1, .. G_k and note that G is parallel composition of the G_i+{s,t}, Recurse | |
| Jul 22, 2010 at 17:44 | history | answered | David Eppstein | CC BY-SA 2.5 |