ECCC-Report TR08-110https://eccc.weizmann.ac.il/report/2008/110Comments and Revisions published for TR08-110en-usTue, 16 Dec 2008 11:26:28 +0200
Paper TR08-110
| A Lower Bound on the Size of Series-Parallel Graphs Dense in Long Paths |
Chris Calabro
https://eccc.weizmann.ac.il/report/2008/110One way to quantify how dense a multidag is in long paths is to find
the largest n, m such that whichever &le; n edges are removed, there is still
a path from an original input to an original output with &ge; m edges
- the larger we can make n, m, the denser is the graph.
For a given n, m, we would like to lower bound the size such a graph, say in edges, at least
when restricting to a particular class of graphs. A bound of &Omega;(n lg m) was
provided in [Val77] for one notion of series-parallel graphs. Here we reprove the
same result but in greater detail and relate that notion of series-parallel
to other popular notions of series-parallel. In particular, we show that
that notion is more general than minimal series-parallel and two terminal
series-parallel.
Tue, 16 Dec 2008 11:26:28 +0200https://eccc.weizmann.ac.il/report/2008/110