2026-08-10T22:19:08Z https://drops.dagstuhl.de/oai

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

PACE Solver Description: Crossy - An Exact Solver for One-Sided Crossing Minimization Röhr, Tobias Simonov, Kirill One-sided Crossing Minimization Exact Algorithms Graph Drawing Incremental MaxSAT We describe Crossy, an exact solver for One-sided Crossing Minimization (OSCM) that ranked 5th in the Parameterized Algorithms and Computational Experiments (PACE) Challenge 2024 (Exact and Parameterized Track). Crossy applies a series of reductions and subsequently transforms the input into an instance of Weighted Directed Feedback Arc Set (WDFAS), which is then formulated in incremental MaxSAT . We use the recently introduced concept of User Propagators for CDCL SAT solvers in order to dynamically add cycle constraints. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tobias Röhr and Kirill Simonov 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.30 urn:nbn:de:0030-drops-222562 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.30 eng https://creativecommons.org/licenses/by/4.0/legalcode