A New Exact Algorithm for the TwoSided Crossing Minimization Problem
Zheng, Lanbo and Buchheim, Christoph
(2007)
A New Exact Algorithm for the TwoSided Crossing Minimization Problem.
Published In:
Combinatorial optimization and applications first international conference, COCOA 2007, Xi'an, China, August 1416, 2007 ; proceedings, Lecture Notes in Computer Science. 4616 Springer 2007, pp. 301310.
Abstract
The TwoSided Crossing Minimization (TSCM) problem calls for minimizing the number of edge crossings of a bipartite graph where the two sets of vertices are drawn on two parallel layers and edges are drawn as straight lines. This wellknown problem has important applications in VLSI design and automatic graph drawing. In this paper, we present a new branchandcut algorithm for the TSCM problem by modeling it directly to a binary quadratic programming problem. We show that a large number of effective cutting planes can be derived based on a reformulation of the TSCM problem. We compare our algorithm with a previous exact algorithm by testing both implementations with the same set of instances. Experimental evaluation demonstrates the effectiveness of our approach.
Item Type:  Proceedings article 

Citations:  [error in script] 8 (Google Scholar)  [error in script] 
Uncontrolled Keywords:  [error in script] 
Subjects: 

Uncontrolled Keywords:  crossing minimization, quadratic binary programming 
Subjects:  68XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R10 Graph theory 90XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C20 Quadratic programming 
Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Juenger 
Depositing User:  Christoph Buchheim 
Date Deposited:  03 May 2007 00:00 
Last Modified:  11 Aug 2011 14:40 
ZAIK Number:  [error in script] 

Depositing User:  Christoph Buchheim 
Date Deposited:  03 May 2007 00:00 
Last Modified:  11 Aug 2011 14:40 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/540 