Zurück zu den Preprints des Jahres 1998


1998-23

A Note on an Extension of Facet-Defining Digraphs

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


Series: 1998-23, Preprints

MSC:
90B10 Network models, 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