Online graph exploration on a restricted graph class: optimal solutions for tadpole graphs

DOI10.1016/J.TCS.2020.06.007MaRDI QIDQ2196574zbMATH OpenOpenAlexFDO

Authors Klaus-Tycho Foerster, Jonathan Maurer, Roger Wattenhofer, Sebastian F. Brandt

Publication date 3 September 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.00581

zbMATH Keywords

graph explorationonline algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Abstract: We study the problem of online graph exploration on undirected graphs, where a searcher has to visit every vertex and return to the origin. Once a new vertex is visited, the searcher learns of all neighboring vertices and the connecting edge weights. The goal such an exploration is to minimize its total cost, where each edge traversal incurs a cost of the corresponding edge weight. We investigate the problem on tadpole graphs (also known as dragons, kites), which consist of a cycle with an attached path. Miyazaki et al. (The online graph exploration problem on restricted graphs, IEICE Transactions 92-D (9), 2009) showed that every online algorithm on these graphs must have a competitive ratio of 2-epsilon, but did not provide upper bounds for non-unit edge weights. We show via amortized analysis that a greedy approach yields a matching competitive ratio of 2 on tadpole graphs, for arbitrary non-negative edge weights.

Recommendations

• Online graph exploration with advice
• Online Graph Exploration: New Results on Old and New Algorithms
• Online graph exploration: New results on old and new algorithms
• Online graph exploration on trees, unicyclic graphs and cactus graphs
• Online graph exploration algorithms for cycles and trees by multiple searchers

Cites work

• Algorithms – ESA 2005
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Constructing competitive tours from local information
• Exploring sparse graphs with advice (extended abstract)
• scientific article; zbMATH DE number 3885963 (Why is no real title available?)
• scientific article; zbMATH DE number 3717369 (Why is no real title available?)
• Lower and upper competitive bounds for online directed graph exploration
• On super edge-magic graphs.
• Online graph exploration with advice
• Online graph exploration: New results on old and new algorithms
• Tight bounds for undirected graph exploration with pebbles and multiple agents
• Treasure hunt with advice
• Weighted nearest neighbor algorithms for the graph exploration problem on cycles
• Wireless evacuation on \(m\) rays with \(k\) searchers

Cited in

(7)

• Online graph exploration: New results on old and new algorithms
• Online graph exploration on trees, unicyclic graphs and cactus graphs
• Online Graph Exploration: New Results on Old and New Algorithms
• An improved upper bound for the online graph exploration problem on unicyclic graphs
• Exploration of graphs with excluded minors
• On time-travel planning in dynamic graphs
• An improved lower bound for competitive graph exploration

This page was built for publication: Online graph exploration on a restricted graph class: optimal solutions for tadpole graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196574)