Back

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.

, 20 pages

Document

G-2005-72.pdf (200 KB)