PACE Solver Description: OCMu64, a Solver for One-Sided Crossing Minimization
OPEN ACCESS
Loading...
Author / Producer
Date
2024
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
Given a bipartite graph (A,B), the one-sided crossing minimization (OCM) problem is to find an ordering of the vertices of B that minimizes the number of edge crossings when drawn in the plane. We introduce the novel strongly fixed, practically fixed, and practically glued reductions that maximally generalize some existing reductions. We apply these in our exact solver OCMu64, that directly uses branch-and-bound on the ordering of the vertices of B and does not depend on ILP or SAT solvers.
Permanent link
Publication status
published
External links
Book title
19th International Symposium on Parameterized and Exact Computation (IPEC 2024)
Volume
321
Pages / Article No.
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
19th International Symposium on Parameterized and Exact Computation (IPEC 2024)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Graph drawing; crossing number; branch and bound
Organisational unit
09568 - Rätsch, Gunnar / Rätsch, Gunnar