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
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 23, 2010 at 10:20 | comment | added | András Salamon | I agree, for edge-series-parallel multigraphs this is linear. Apologies for the incorrect categorical statement that this approach isn't linear. | |
| Jul 23, 2010 at 0:12 | vote | accept | Gordon Royle | ||
| Jul 23, 2010 at 0:11 | comment | added | Gordon Royle | I agree... having now thought about it more carefully this idea easily gives a linear algorithm. Run Valdes et. al. recognition algorithm to reduce the graph to a single edge, keeping track at each stage of which pair of edges were merged. Then build the tree by reversing these steps, with each stage involving creating one new internal node and one new leaf node, and adjusting pointers on three nodes, all of which is constant time. Of course it's obvious now I understand it, but is this why nobody bothers to write it down? | |
| Jul 22, 2010 at 17:37 | comment | added | David Eppstein | I don't see what the trouble here is. This looks very linear to me. All you need is to maintain pointers between edges of G' and the corresponding nodes of T' so that you can perform each step in constant time. | |
| Jul 22, 2010 at 12:53 | comment | added | András Salamon | Yes, this is the basic idea of the algorithms that have been published over the last few decades. The tricky part is how to do this efficiently: a naive approach is certainly not linear. | |
| Jul 22, 2010 at 12:22 | history | answered | David E Speyer | CC BY-SA 2.5 |