A Polyhedral Approach to the Multi-Layer Crossing Minimization Problem

Jünger, Michael and Lee, Eva K. and Mutzel, Petra and Odenthal, Thomas (1997) A Polyhedral Approach to the Multi-Layer Crossing Minimization Problem.
Published In: Graph drawing : 5th international symposium, GD '97, Rome, Italy, September 18 - 20, 1997 ; proceedings, Lecture notes in computer science. 1353 Springer 1997, pp. 13-24.

Abstract

We study the multi-layer crossing minimization problem from a polyhedral point of view. After the introduction of an integer programming formulation of the multi-layer crossing minimization problem, we examine the 2-layer case and derive several classes of facets of the associated polytope. Preliminary computational results for 2- and 3-layer instances indicate, that the usage of the corresponding facet-defining inequalities in a branch-and-cut approach may only lead to a practically useful algorithm, if deeper polyhedral studies are conducted.


Actions:
Download: [img] Postscript - Preprinted Version
Download (185kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Proceedings article
Citations: [error in script] 48 (Google Scholar) | [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
Uncontrolled Keywords: branch-and-cut, crossing number, linear ordering
Subjects: UNSPECIFIED
Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 24 Jun 2003 00:00
Last Modified: 19 Jan 2012 09:42
Deposit Information:
ZAIK Number: [error in script]
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 24 Jun 2003 00:00
Last Modified: 19 Jan 2012 09:42
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/299