G-2005-57
Polyhedra for the Equivalent Subgraph Problem
BibTeX reference
We give some properties of the equivalent subgraph polytope and its dominant. We characterize those digraphs whose corresponding polyhedra are completely described by bound and trivial dicut inequalities. We give complete descriptions of the equivalent subgraph polyhedra for a class of digraphs which includes directed Halin graphs. As well we derive the description of the dominant of the dicut polytope and we show that the equivalent subgraph problem is polynomially solvable for this class.
Published August 2005 , 24 pages
Document
G-2005-57.pdf (200 KB)