Drawing maps with advice

DOI10.1016/j.jpdc.2011.10.004zbMath1242.68192OpenAlexW2046334554MaRDI QIDQ433400

Andrzej Pelc, Dariusz Dereniowski

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

spanning treegraph drawingadvicetopology recognition

Mathematics Subject Classification ID

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

Related Items (12)

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 ⋮ Treasure hunt in graph using pebbles ⋮ Impact of knowledge on election time in anonymous networks ⋮ Short labeling schemes for topology recognition in wireless tree networks ⋮ Topology recognition and leader election in colored networks ⋮ Setting Ports in an Anonymous Network: How to Reduce the Level of Symmetry? ⋮ Distinguishing views in symmetric networks: a tight lower bound ⋮ Advice complexity of maximum independent set in sparse and bipartite graphs ⋮ Distributed graph searching with a sense of direction ⋮ Topology recognition with advice

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed enumeration
• Trade-offs between the size of advice and broadcasting time in trees
• Local MST computation with short advice
• Optimal graph exploration without good maps
• Tree exploration with advice
• Fast radio broadcasting with advice
• Graph searching with advice
• Universal covers of graphs: Isomorphism to depth \(n-1\) implies isomorphism to all depths
• The power of a pebble: Exploring and mapping directed graphs
• Proof labeling schemes
• Distributed computing with advice: information sensitivity of graph coloring
• Approximate distance oracles
• Undirected connectivity in log-space
• Online Computation with Advice
• Labeling Schemes for Flow and Connectivity
• Exploring an unknown graph
• Discrete Mathematics
• Distance labeling in graphs
• Exploring Unknown Environments
• How to meet when you forget
• Oracle size
• Compact Labeling Scheme for Ancestor Queries
• Automata, Languages and Programming
• Fibrations of graphs

This page was built for publication: Drawing maps with advice