Title
Measuring the Distance to Series-Parallelity by Path
Expressions
Author
Valeska Naumann
Publication
Lecture Notes in Computer Science 903, Proc. 20th International Workshop on Graph-Theoretic
Concepts in Computer Science (WG'94), ed. E.W. Mayr, 1994, pp. 269-281
Source
-
Classification
-
not available
Keywords
-
not available
-
-
Many graph and network problems are easily solved in
the special case of series-parallel networks, but are
highly intractable in the general case. This paper
considers two complexity measures of two-terminal
directed acyclic graphs (st-dags) describing the
"distance" of an st-dag from series-parallelity. The
two complexity measures are the factoring
complexity psi(G) and the reduction complexity
mu (G). Bein, Kamburowski, and Stallmann have
shown that psi (G) leq mu (G) leq n-3, where G
is an st-dag with n nodes. They conjectured that
psi (G) = mu (G). This paper gives a proof for this
conjecture.
