98-23
A Note on an Extension of Facet-Defining Digraphs
by Girlich, E.; Kovalev, M.; Nalivaiko, V.
Preprint series: 98-23, Preprints
- MSC:
- 90B10 Flows in networks, deterministic
Abstract: In this paper we present sufficient conditions for unweighted digraphs to induce \fdi s of the linear ordering polytope $\Pn$. We introduce constructive operations ({\em Identification (of nodes),\extend}) for generating new facets of $\Pn$ by using already known facets. The identification generates new digraphs by identification two nodes of the source digraph and presented for arbitrary unweighted digraphs. On examples of \ml s we show a possible way to find two nodes, which can be identified to obtain new \fdd. By connecting M bius ladders with special digraphs \extend\ generates new facet-defining digraphs to which we can apply \extend{} repeatedly.
Keywords: Linear ordering polytope, Möbius ladders, feedback arc set
Notes: submitted to: Optimization
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.