An improved lower bound for competitive graph exploration
From MaRDI portal
Publication:831137
DOI10.1016/j.tcs.2021.04.003zbMath1502.68211arXiv2002.10958OpenAlexW3153676396MaRDI QIDQ831137
Alexander V. Hopp, Alexander Birx, Christina Karousatou, Yann Disser
Publication date: 10 May 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2002.10958
Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)
Related Items (1)
Cites Work
- 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
- On the nearest neighbor rule for the traveling salesman problem
- Exploring sparse graphs with advice (extended abstract)
- Online graph exploration: New results on old and new algorithms
- Online graph exploration on a restricted graph class: optimal solutions for tadpole graphs
- Online graph exploration algorithms for cycles and trees by multiple searchers
- Fast collaborative graph exploration
- Graph exploration by a finite automaton
- Online Graph Exploration with Advice
- Collective tree exploration
- Undirected connectivity in log-space
- An Analysis of Several Heuristics for the Traveling Salesman Problem
- Tight Bounds for Online TSP on the Line
- Deterministic Graph Exploration with Advice
- Exploring an unknown graph
- Exploring Unknown Environments
- Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents
- Why Robots Need Maps
- Algorithms – ESA 2005
- A Recursive Approach to Multi-robot Exploration of Trees
- A general lower bound for collaborative tree exploration
This page was built for publication: An improved lower bound for competitive graph exploration
