G-2005-72
The Steiner Equivalent Subgraph Polyhedra for Series-Parallel Digraphs
BibTeX reference
We give complete descriptions of the Steiner equivalent subgraph polytope and its dominant when the underlying digraph is strongly connected and series-parallel. These descriptions show that the Steiner equivalent subgraph problem is polynomially solvable on such digraphs and lead as well to the description of the dominant of the Steiner dicut poytope for this class of digraphs.
Published September 2005 , 20 pages
Document
G-2005-72.pdf (200 KB)