Groupe d’études et de recherche en analyse des décisions

G-2005-72

The Steiner Equivalent Subgraph Polyhedra for Series-Parallel Digraphs

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