1 Search Results for "Wetzels, Florian"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.15
Comparative Design-Choice Analysis of Color Refinement Algorithms Beyond the Worst Case

Authors: Markus Anders, Pascal Schweitzer, and Florian Wetzels

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
Color refinement is a crucial subroutine in symmetry detection in theory as well as practice. It has further applications in machine learning and in computational problems from linear algebra. While tight lower bounds for the worst case complexity are known [Berkholz, Bonsma, Grohe, ESA2013] no comparative analysis of design choices for color refinement algorithms is available. We devise two models within which we can compare color refinement algorithms using formal methods, an online model and an approximation model. We use these to show that no online algorithm is competitive beyond a logarithmic factor and no algorithm can approximate the optimal color refinement splitting scheme beyond a logarithmic factor. We also directly compare strategies used in practice showing that, on some graphs, queue based strategies outperform stack based ones by a logarithmic factor and vice versa. Similar results hold for strategies based on priority queues.
Cite as

Markus Anders, Pascal Schweitzer, and Florian Wetzels. Comparative Design-Choice Analysis of Color Refinement Algorithms Beyond the Worst Case. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{anders_et_al:LIPIcs.ICALP.2021.15,
  author =	{Anders, Markus and Schweitzer, Pascal and Wetzels, Florian},
  title =	{{Comparative Design-Choice Analysis of Color Refinement Algorithms Beyond the Worst Case}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.15},
  URN =		{urn:nbn:de:0030-drops-140846},
  doi =		{10.4230/LIPIcs.ICALP.2021.15},
  annote =	{Keywords: Color refinement, Online algorithms, Graph isomorphism, Lower bounds}
}
  • Refine by Author
  • 1 Anders, Markus
  • 1 Schweitzer, Pascal
  • 1 Wetzels, Florian

  • Refine by Classification
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 1 Color refinement
  • 1 Graph isomorphism
  • 1 Lower bounds
  • 1 Online algorithms

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact