Tree exploration with advice

DOI10.1016/j.ic.2008.07.005zbMath1169.68047OpenAlexW2038319432MaRDI QIDQ958304

Pierre Fraigniaud, David Ilcinkas, Andrzej Pelc

Publication date: 3 December 2008

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

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

zbMATH Keywords

exploration algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Byzantine gathering in polynomial time ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ Finding the size and the diameter of a radio network using short labels ⋮ Four shades of deterministic leader election in anonymous networks ⋮ Fast rendezvous with advice ⋮ Unnamed Item ⋮ Advice complexity of adaptive priority algorithms ⋮ Online search with a hint ⋮ Lower and upper bounds for deterministic convergecast with labeling schemes ⋮ Drawing maps with advice ⋮ LABEL-GUIDED GRAPH EXPLORATION WITH ADJUSTABLE RATIO OF LABELS ⋮ Impact of knowledge on election time in anonymous networks ⋮ Fast radio broadcasting with advice ⋮ Communication algorithms with advice ⋮ Short labeling schemes for topology recognition in wireless tree networks ⋮ Black Hole Search in Directed Graphs ⋮ Advice complexity of maximum independent set in sparse and bipartite graphs ⋮ Exploring sparse graphs with advice ⋮ Introduction to local certification ⋮ Topology recognition with advice

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Local MST computation with short advice
• Optimal graph exploration without good maps
• Shortest paths without a map
• Piecemeal graph exploration by a mobile robot.
• The power of a pebble: Exploring and mapping directed graphs
• Sense of direction in distributed computing
• Optimal deterministic broadcasting in known topology radio networks
• How to learn an unknown environment. I
• Online Navigation in a Room
• Navigating in Unfamiliar Geometric Terrain
• Impact of topographic information on graph exploration efficiency
• Exploring an unknown graph
• Tree exploration with little memory
• Exploring Unknown Undirected Graphs
• Exploring Unknown Environments
• Hundreds of impossibility results for distributed computing
• Faster communication in known topology radio networks
• Oracle size
• Graph Searching with Advice
• Distributed Computing with Advice: Information Sensitivity of Graph Coloring
• Algorithms – ESA 2005
• Broadcasting algorithms in radio networks with unknown topology