An improved lower bound for competitive graph exploration

DOI10.1016/J.TCS.2021.04.003MaRDI QIDQ831137zbMATH OpenOpenAlexFDO

Authors Alexander Birx, Y. Disser, Alexander V. Hopp, Christina Karousatou

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

zbMATH Keywords

online algorithmscompetitive analysiscompetitive ratiograph exploration

Mathematics Subject Classification ID

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

Abstract: We give an improved lower bound of 10/3 on the competitive ratio for the exploration of an undirected, edge-weighted graph with a single agent that needs to return to the starting location after visiting all vertices. We assume that the agent has full knowledge of all edges incident to visited vertices, and, in particular, vertices have unique identifiers. Our bound improves a lower bound of 2.5 by Dobrev et al. [SIROCCO'12] and also holds for planar graphs, where it complements an upper bound of 16 by Kalyanasundaram and Pruhs[TCS'94]. The question whether a constant competitive ratio can be achieved in general remains open.

Recommendations

• Online Graph Exploration: New Results on Old and New Algorithms
• Lower and upper competitive bounds for online directed graph exploration
• Online graph exploration: New results on old and new algorithms
• Online graph exploration with advice
• Constructing competitive tours from local information

Cites work

• A general lower bound for collaborative tree exploration
• A recursive approach to multi-robot exploration of trees
• Algorithms – ESA 2005
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Collective tree exploration
• Constructing competitive tours from local information
• Deterministic graph exploration with advice
• Exploring Unknown Environments
• Exploring an unknown graph
• Exploring sparse graphs with advice (extended abstract)
• Fast collaborative graph exploration
• Graph exploration by a finite automaton
• Lower and upper competitive bounds for online directed graph exploration
• On the nearest neighbor rule for the traveling salesman problem
• Online graph exploration algorithms for cycles and trees by multiple searchers
• Online graph exploration on a restricted graph class: optimal solutions for tadpole graphs
• Online graph exploration with advice
• Online graph exploration: New results on old and new algorithms
• Tight bounds for online TSP on the line
• Tight bounds for undirected graph exploration with pebbles and multiple agents
• Undirected connectivity in log-space
• Weighted nearest neighbor algorithms for the graph exploration problem on cycles
• Why Robots Need Maps

Cited in

(4)

• Exploring sparse graphs with advice
• A general lower bound for collaborative tree exploration
• An improved upper bound for the online graph exploration problem on unicyclic graphs
• Lower and upper competitive bounds for online directed graph exploration

This page was built for publication: An improved lower bound for competitive graph exploration

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