A Note on an Extension of Facet-Defining Digraphs

by Girlich, E.; Kovalev, M.; Nalivaiko, V.


Preprint series: 98-23, Preprints

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.

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster