Exploring sparse graphs with advice

DOI10.1016/J.IC.2022.104950OpenAlexW4292845823MaRDI QIDQ2105435FDOQ2105435

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

Publication date: 8 December 2022

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

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)

Cites Work

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

Cited In (3)

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

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)