2026-08-18T02:58:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22261 2024-12-05T15:32:42Z ddc:004 open_access

PACE Solver Description: OCMu64, a Solver for One-Sided Crossing Minimization Groot Koerkamp, Ragnar de Vries, Mees Graph drawing crossing number branch and bound 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ragnar Groot Koerkamp and Mees de Vries 2024 Is Part Of LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2024.35 urn:nbn:de:0030-drops-222616 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.35 eng https://creativecommons.org/licenses/by/4.0/legalcode