Lower Bounds for Graph Exploration Using Local Policies

DOI10.1007/978-3-319-30139-6_5zbMath1475.68228arXiv1603.05944OpenAlexW2303801785WikidataQ114917804 ScholiaQ114917804MaRDI QIDQ2803810

Daniela Maftuleac, Aditya Kumar Akash, Sándor P. Fekete, Seoung Kyou Lee, James McLurkin, Alejandro López-Ortiz

Publication date: 3 May 2016

Published in: Journal of Graph Algorithms and Applications, WALCOM: Algorithms and Computation (Search for Journal in Brave)

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

zbMATH Keywords

exploration path

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99) Random walks on graphs (05C81)

Cites Work

• Derandomizing random walks in undirected graphs using locally fair exploration strategies
• A distributed ant algorithm for efficiently patrolling a network
• Workshop on Algorithms and Models for the Web Graph