Buchheim, Christoph ORCID: 0000-0001-9974-404X and Zheng, Lanbo (2006). Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem. In: Computing and combinatorics : 12th annual international conference, COCOON 2006, Taipei, Taiwan, August 15 - 18, 2006 ; proceedings, pp. 507-516. Springer.

[img]
Preview
PDF
zaik2006-522.pdf - Submitted Version

Download (216kB) | Preview

Abstract

Many real-life scheduling, routing and locating problems can be formulated as combinatorial optimization problems whose goal is to find a linear layout of an input graph in such a way that the number of edge crossings is minimized. In this paper, we study a restricted version of the linear layout problem where the order of vertices on the line is fixed, the so-called fixed linear crossing number problem (FLCNP). We show that this NP-hard problem can be reduced to the well-known maximum cut problem. The latter problem was intensively studied in the literature; practically efficient exact algorithms based on the branch-and-cut technique have been developed. By an experimental evaluation on a variety of graphs, we prove that using this reduction for solving FLCNP compares favorably to earlier branch-and-bound algorithms.

Item Type: Book Section, Proceedings Item or annotation in a legal commentary
Creators:
CreatorsEmailORCIDORCID Put Code
Buchheim, ChristophUNSPECIFIEDorcid.org/0000-0001-9974-404XUNSPECIFIED
Zheng, LanboUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
URN: urn:nbn:de:hbz:38-548994
Title of Book: Computing and combinatorics : 12th annual international conference, COCOON 2006, Taipei, Taiwan, August 15 - 18, 2006 ; proceedings
Series Name: Lecture Notes in Computer Science
Volume: 4112
Page Range: pp. 507-516
Date: 2006
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/54899

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item