An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization

Dujmović, Vida and Whitesides, Sue (2002) An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002 , pp. 118-129(Official URL: http://dx.doi.org/10.1007/3-540-36151-0_12).

Full text not available from this repository.

Abstract

We give an O(øk · n 2) algorithm for the 1-SIDED CROSSING MINIMIZATION problem, thus showing that the problem is Fixed Parameter Tractable. The constant \phi in the running time is the golden ratio \phi=\frac{1+\sqrt{5}}{2}\approx 1.618. The constant k is the parameter of the problem: the number of allowed edge crossings.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-36151-0_12
Classifications: M Methods > M.999 Others
Z Theory > Z.999 Others
G Algorithms and Complexity > G.420 Crossings
URI: http://gdea.informatik.uni-koeln.de/id/eprint/294

Actions (login required)

View Item View Item