2026-07-25T01:58:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18664 2024-03-06T11:02:24Z ddc:004 open_access

Exploration of Graphs with Excluded Minors Baligács, Júlia Disser, Yann Heinrich, Irene Schweitzer, Pascal online algorithms competitive analysis graph exploration graph spanners minor-free graphs bounded genus graphs 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Júlia Baligács and Yann Disser and Irene Heinrich and Pascal Schweitzer 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.11 urn:nbn:de:0030-drops-186644 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.11 eng https://creativecommons.org/licenses/by/4.0/legalcode