Exploring sparse graphs with advice

DOI10.1016/J.IC.2022.104950MaRDI QIDQ2105435zbMATH OpenOpenAlexFDO

Authors Hans-Joachim Böckenhauer, Janosch Fuchs, Walter Unger

Publication date 8 December 2022

Published in Information and Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.ic.2022.104950

zbMATH Keywords

advice complexitygraph explorationfixed-graph scenario

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Exploring sparse graphs with advice (extended abstract)
• Online graph exploration with advice
• Deterministic Graph Exploration with Advice
• Deterministic graph exploration with advice
• Edge exploration of a graph by mobile agent

Cites work

• Algorithms – ESA 2005
• An improved lower bound for competitive graph exploration
• Constructing competitive tours from local information
• Deterministic Graph Exploration with Advice
• Exploring Unknown Environments
• Exploring sparse graphs with advice (extended abstract)
• How Much Information about the Future Is Needed?
• Information complexity of online problems
• Lower and upper competitive bounds for online directed graph exploration
• Map construction of unknown graphs by multiple agents
• Navigating in Unfamiliar Geometric Terrain
• Network exploration by silent and oblivious robots
• On the Advice Complexity of Online Problems
• Online computation with advice
• Online graph exploration with advice
• Online graph exploration: New results on old and new algorithms
• STACS 2004
• The power of a pebble: Exploring and mapping directed graphs
• Treasure hunt with advice
• Tree exploration with advice
• Tree exploration with little memory

Cited in

(3)

• An improved upper bound for the online graph exploration problem on unicyclic graphs
• Deterministic Graph Exploration with Advice
• Graph Searching with Advice

This page was built for publication: Exploring sparse graphs with advice

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