Universität zu Köln

Jünger, Michael and Mutzel, Petra ORCID: 0000-0001-7621-971X (1996). Exact and Heuristic Algorithms for 2-Layer Straightline Crossing Minimization. Springer. ["eprint_fieldopt_monograph_type_preprint" not defined].

Preview

PDF zpr95-203.pdf - Submitted Version Download (208kB) | Preview

Abstract

We present algorithms for the 2-layer straightline crossing minimization problem that are able to compute exact optima. Our computational results lead us to the conclusion that there is no need for heuristics if one layer is fixed, even though the problem is NP-hard, and that for the general problem with two variable layers, true optima can be computed for sparse instances in which the smaller layer contains up to 15 nodes. For bigger instances, the iterated barycenter method turns out to be the method of choice among several popular heuristics whose performance we could assess by comparing the results to optimum solutions.

Item Type:	Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined])
Creators:	Creators Email ORCID ORCID Put Code Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Mutzel, Petra UNSPECIFIED orcid.org/0000-0001-7621-971X UNSPECIFIED
URN:	urn:nbn:de:hbz:38-547002
Series Name:	Lecture notes in computer science
Volume:	1027
Page Range:	pp. 337-348
Date:	1996
Publisher:	Springer
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54700