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:  8 (Google Scholar)  2 (Web of Science) 
Uncontrolled Keywords:  crossing minimization quadratic binary programming 
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Juenger 
Related URLs: 
ZAIK Number:  zaik2007540 

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 