Distinguishing views in symmetric networks: a tight lower bound

DOI10.1016/j.tcs.2015.03.018zbMath1310.68158arXiv1407.2511OpenAlexW2028631314MaRDI QIDQ2342668

Adrian Kosowski, Dominik Pająk, Dariusz Dereniowski

Publication date: 29 April 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1407.2511

zbMATH Keywords

quotient graphanonymous networkviewport-labeled network

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)

Related Items

Distinguishing arc-colourings of symmetric digraphs, Knowledge, level of symmetry, and time of leader election, Topology recognition and leader election in colored networks, Setting Ports in an Anonymous Network: How to Reduce the Level of Symmetry?, Proper distinguishing arc-colourings of symmetric digraphs

Cites Work

• Unnamed Item
• Drawing maps with advice
• Knowledge, level of symmetry, and time of leader election
• Universal covers of graphs: Isomorphism to depth \(n-1\) implies isomorphism to all depths
• Computing on anonymous networks with sense of direction
• How to meet when you forget: log-space rendezvous in arbitrary graphs
• Leader election for anonymous asynchronous agents in arbitrary networks
• Decidability Classes for Mobile Agents Computing
• Exact Quantum Algorithms for the Leader Election Problem
• Computing functions on asynchronous anonymous networks
• Universal dynamic synchronous self-stabilization
• Effective Elections for Anonymous Mobile Agents
• Fibrations of graphs