Search Results

Documents authored by Blanco, Thorgal


Document
PACE Solver Description
PACE Solver Description: LUNCH - Linear Uncrossing Heuristics

Authors: Kenneth Langedal, Matthias Bentert, Thorgal Blanco, and Pål Grønås Drange

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


Abstract
The 2024 PACE challenge is on One-Sided Crossing Minimization: Given a bipartite graph with one fixed and one free layer, compute an ordering of the vertices in the free layer that minimizes the number of edge crossings in a straight-line drawing of the graph. Here, we briefly describe our exact, parameterized, and heuristic submissions. The main contribution is an efficient reduction to a weighted version of Directed Feedback Arc Set, allowing us to detect subproblems that can be solved independently.

Cite as

Kenneth Langedal, Matthias Bentert, Thorgal Blanco, and Pål Grønås Drange. PACE Solver Description: LUNCH - Linear Uncrossing Heuristics. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 34:1-34:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{langedal_et_al:LIPIcs.IPEC.2024.34,
  author =	{Langedal, Kenneth and Bentert, Matthias and Blanco, Thorgal and Drange, P\r{a}l Gr{\o}n\r{a}s},
  title =	{{PACE Solver Description: LUNCH - Linear Uncrossing Heuristics}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{34:1--34: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.34},
  URN =		{urn:nbn:de:0030-drops-222608},
  doi =		{10.4230/LIPIcs.IPEC.2024.34},
  annote =	{Keywords: graph drawing, feedback arc set, algorithm engineering}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail