G-2005-72
The Steiner Equivalent Subgraph Polyhedra for Series-Parallel Digraphs
référence BibTeX
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.
Paru en septembre 2005 , 20 pages
Document
G-2005-72.pdf (190 Ko)