2 Search Results for "Dobler, Alexander"


Document
PACE Solver Description
PACE Solver Description: Touiouidth

Authors: Gaétan Berthe, Yoann Coudert-Osmont, Alexander Dobler, Laure Morelle, Amadeus Reinald, and Mathis Rocton

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)


Abstract
We describe Touiouidth, a twin-width solver for the exact-track of the 2023 PACE Challenge: Twin Width. Our solver is based on a simple branch and bound algorithm with search space reductions and is implemented in C++.

Cite as

Gaétan Berthe, Yoann Coudert-Osmont, Alexander Dobler, Laure Morelle, Amadeus Reinald, and Mathis Rocton. PACE Solver Description: Touiouidth. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 38:1-38:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{berthe_et_al:LIPIcs.IPEC.2023.38,
  author =	{Berthe, Ga\'{e}tan and Coudert-Osmont, Yoann and Dobler, Alexander and Morelle, Laure and Reinald, Amadeus and Rocton, Mathis},
  title =	{{PACE Solver Description: Touiouidth}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{38:1--38:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.38},
  URN =		{urn:nbn:de:0030-drops-194576},
  doi =		{10.4230/LIPIcs.IPEC.2023.38},
  annote =	{Keywords: Twinwidth, Pace Challenge}
}
Document
Turbocharging Heuristics for Weak Coloring Numbers

Authors: Alexander Dobler, Manuel Sorge, and Anaïs Villedieu

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)


Abstract
Bounded expansion and nowhere-dense classes of graphs capture the theoretical tractability for several important algorithmic problems. These classes of graphs can be characterized by the so-called weak coloring numbers of graphs, which generalize the well-known graph invariant degeneracy (also called k-core number). Being NP-hard, weak-coloring numbers were previously computed on real-world graphs mainly via incremental heuristics. We study whether it is feasible to augment such heuristics with exponential-time subprocedures that kick in when a desired upper bound on the weak coloring number is breached. We provide hardness and tractability results on the corresponding computational subproblems. We implemented several of the resulting algorithms and show them to be competitive with previous approaches on a previously studied set of benchmark instances containing 86 graphs with up to 183831 edges. We obtain improved weak coloring numbers for over half of the instances.

Cite as

Alexander Dobler, Manuel Sorge, and Anaïs Villedieu. Turbocharging Heuristics for Weak Coloring Numbers. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{dobler_et_al:LIPIcs.ESA.2022.44,
  author =	{Dobler, Alexander and Sorge, Manuel and Villedieu, Ana\"{i}s},
  title =	{{Turbocharging Heuristics for Weak Coloring Numbers}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{44:1--44:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.44},
  URN =		{urn:nbn:de:0030-drops-169820},
  doi =		{10.4230/LIPIcs.ESA.2022.44},
  annote =	{Keywords: Structural sparsity, parameterized algorithms, parameterized complexity, fixed-parameter tractability}
}
  • Refine by Author
  • 2 Dobler, Alexander
  • 1 Berthe, Gaétan
  • 1 Coudert-Osmont, Yoann
  • 1 Morelle, Laure
  • 1 Reinald, Amadeus
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 Pace Challenge
  • 1 Structural sparsity
  • 1 Twinwidth
  • 1 fixed-parameter tractability
  • 1 parameterized algorithms
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2022
  • 1 2023

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