DROPS

Document

PACE Solver Description

DOI: 10.4230/LIPIcs.IPEC.2024.30

PACE Solver Description: Crossy - An Exact Solver for One-Sided Crossing Minimization

Authors: Tobias Röhr and Kirill Simonov

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract

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.

Cite as

Tobias Röhr and Kirill Simonov. PACE Solver Description: Crossy - An Exact Solver for One-Sided Crossing Minimization. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 30:1-30:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{rohr_et_al:LIPIcs.IPEC.2024.30,
  author =	{R\"{o}hr, Tobias and Simonov, Kirill},
  title =	{{PACE Solver Description: Crossy - An Exact Solver for One-Sided Crossing Minimization}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{30:1--30:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.30},
  URN =		{urn:nbn:de:0030-drops-222562},
  doi =		{10.4230/LIPIcs.IPEC.2024.30},
  annote =	{Keywords: One-sided Crossing Minimization, Exact Algorithms, Graph Drawing, Incremental MaxSAT}
}

Search Results

Documents authored by Röhr, Tobias

PACE Solver Description: Crossy - An Exact Solver for One-Sided Crossing Minimization

Abstract

Cite as

Thanks for your feedback!

Could not send message