Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem

Buchheim, Christoph and Zheng, Lanbo (2006) Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem.
Published In: Computing and combinatorics : 12th annual international conference, COCOON 2006, Taipei, Taiwan, August 15 - 18, 2006 ; proceedings, Lecture Notes in Computer Science. 4112 Springer 2006, pp. 507-516.

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.


Actions:
Download: [img] PDF - Preprinted Version
Download (216kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Proceedings article
Citations: [error in script] 5 (Google Scholar) | [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
  • 05-XX Combinatorics > 05Cxx Graph theory > 05C85 Graph algorithms

  • Uncontrolled Keywords: crossing minimization, max cut
    Subjects: 05-XX Combinatorics > 05Cxx Graph theory > 05C85 Graph algorithms
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
    Depositing User: Christoph Buchheim
    Date Deposited: 22 Jun 2006 00:00
    Last Modified: 12 Jan 2012 09:32
    Deposit Information:
    ZAIK Number: [error in script]
    Depositing User: Christoph Buchheim
    Date Deposited: 22 Jun 2006 00:00
    Last Modified: 12 Jan 2012 09:32
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/522