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

DOI10.1016/j.tcs.2020.06.007zbMath1453.68214arXiv1903.00581OpenAlexW3036524578MaRDI QIDQ2196574

Roger Wattenhofer, Jonathan Maurer, Klaus-Tycho Foerster, 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

online algorithmsgraph exploration

Mathematics Subject Classification ID

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

Related Items (2)

An improved lower bound for competitive graph exploration ⋮ Online graph exploration on trees, unicyclic graphs and cactus graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower and upper competitive bounds for online directed graph exploration
• Weighted nearest neighbor algorithms for the graph exploration problem on cycles
• Constructing competitive tours from local information
• Exploring sparse graphs with advice (extended abstract)
• Online graph exploration: New results on old and new algorithms
• Online Graph Exploration with Advice
• Treasure Hunt with Advice
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents
• Algorithms – ESA 2005
• Wireless evacuation on \(m\) rays with \(k\) searchers

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