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
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 23, 2010 at 10:12 | comment | added | András Salamon | Ah, you are asking about edge-series-parallel multigraphs. Valdes/Tarjan/Lawler start with vertex-series-parallel digraphs, turn these into edge-series-parallel multidigraphs by taking the line digraph, then work with these (they are trying to avoid the overhead of taking the transitive closure). The VTL approach is easier if you are starting with the multigraph. Modular decomposition is a general approach that applies to 2-structures, undirected graphs, posets, as well as directed graphs (anywhere where the idea of a module makes sense). | |
| Jul 22, 2010 at 13:37 | comment | added | Gordon Royle | Are we talking about the same thing here? I thought modular decompositions were related to cographs where "series composition" essentially means "disjoint union" and "parallel composition" essentially means "complete join". Here, I have two graphs with distinguished terminals (G,s,t) and (H,s',t') and the parallel composition identifies s with s' and t with t' but creates a new graph with these as the terminals. The series composition identifies t with s' and creates a new graph with s and t' as terminals (and t=s' as a cutvertex). | |
| Jul 22, 2010 at 13:17 | history | edited | András Salamon | CC BY-SA 2.5 |
add release info for Sage
|
| Jul 22, 2010 at 8:23 | history | answered | András Salamon | CC BY-SA 2.5 |