Drawing maps with advice

DOI10.1016/J.JPDC.2011.10.004zbMATH Open1242.68192OpenAlexW2046334554MaRDI QIDQ433400FDOQ433400

Authors Dariusz Dereniowski, Andrzej Pelc

Publication date 13 July 2012

Published in Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jpdc.2011.10.004

zbMATH Keywords

advicetopology recognitionspanning treegraph drawing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Mathematical problems of computer architecture (68M07) Network design and communication in computer systems (68M10)

Recommendations

• Drawing maps with advice
• Deterministic Graph Exploration with Advice
• Deterministic graph exploration with advice
• Edge exploration of a graph by mobile agent
• Map construction of unknown graphs by multiple agents

Cites work

• scientific article; zbMATH DE number 5999543 (Why is no real title available?)
• scientific article; zbMATH DE number 2006642 (Why is no real title available?)
• scientific article; zbMATH DE number 3005477 (Why is no real title available?)
• scientific article; zbMATH DE number 2087429 (Why is no real title available?)
• An efficient message passing election algorithm based on Mazurkiewicz's algorithm
• Approximate distance oracles
• Automata, Languages and Programming
• Compact Labeling Scheme for Ancestor Queries
• Discrete Mathematics
• Distance labeling in graphs
• Distributed computing with advice: information sensitivity of graph coloring
• Distributed enumeration
• Exploring Unknown Environments
• Exploring an unknown graph
• Fast radio broadcasting with advice
• Fibrations of graphs
• Graph searching with advice
• How to meet when you forget: log-space rendezvous in arbitrary graphs
• Labeling Schemes for Flow and Connectivity
• Local MST computation with short advice
• Online Computation with Advice
• Optimal graph exploration without good maps
• Oracle size, a new measure of difficulty for communication tasks
• Proof labeling schemes
• The power of a pebble: Exploring and mapping directed graphs
• Trade-offs between the size of advice and broadcasting time in trees
• Tree exploration with advice
• Undirected connectivity in log-space
• Universal covers of graphs: Isomorphism to depth \(n-1\) implies isomorphism to all depths

Cited in

(15)

• Local Maps: New Insights into Mobile Agent Algorithms
• Finding the size and the diameter of a radio network using short labels
• Map construction of unknown graphs by multiple agents
• Four shades of deterministic leader election in anonymous networks
• Distributed graph searching with a sense of direction
• Advice complexity of maximum independent set in sparse and bipartite graphs
• Drawing maps with advice
• Setting ports in an anonymous network: how to reduce the level of symmetry?
• scientific article; zbMATH DE number 1974103 (Why is no real title available?)
• Fast rendezvous with advice
• Distinguishing views in symmetric networks: a tight lower bound
• Topology recognition and leader election in colored networks
• Topology recognition with advice
• Treasure hunt in graph using pebbles
• Impact of knowledge on election time in anonymous networks

This page was built for publication: Drawing maps with advice

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