1 Search Results for "Baligács, Júlia"

Document
DOI: 10.4230/LIPIcs.ESA.2023.11
Exploration of Graphs with Excluded Minors

Authors: Júlia Baligács, Yann Disser, Irene Heinrich, and Pascal Schweitzer

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
We study the online graph exploration problem proposed by Kalyanasundaram and Pruhs (1994) and prove a constant competitive ratio on minor-free graphs. This result encompasses and significantly extends the graph classes that were previously known to admit a constant competitive ratio. The main ingredient of our proof is that we find a connection between the performance of the particular exploration algorithm Blocking and the existence of light spanners. Conversely, we exploit this connection to construct light spanners of bounded genus graphs. In particular, we achieve a lightness that improves on the best known upper bound for genus g ≥ 1 and recovers the known tight bound for the planar case (g = 0).
Cite as

Júlia Baligács, Yann Disser, Irene Heinrich, and Pascal Schweitzer. Exploration of Graphs with Excluded Minors. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 11:1-11:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{baligacs_et_al:LIPIcs.ESA.2023.11,
  author =	{Balig\'{a}cs, J\'{u}lia and Disser, Yann and Heinrich, Irene and Schweitzer, Pascal},
  title =	{{Exploration of Graphs with Excluded Minors}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.11},
  URN =		{urn:nbn:de:0030-drops-186644},
  doi =		{10.4230/LIPIcs.ESA.2023.11},
  annote =	{Keywords: online algorithms, competitive analysis, graph exploration, graph spanners, minor-free graphs, bounded genus graphs}
}
  • Refine by Author
  • 1 Baligács, Júlia
  • 1 Disser, Yann
  • 1 Heinrich, Irene
  • 1 Schweitzer, Pascal

  • Refine by Classification
  • 1 Mathematics of computing → Graphs and surfaces
  • 1 Theory of computation → Online algorithms
  • 1 Theory of computation → Sparsification and spanners

  • Refine by Keyword
  • 1 bounded genus graphs
  • 1 competitive analysis
  • 1 graph exploration
  • 1 graph spanners
  • 1 minor-free graphs
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 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
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact