Universal covers of graphs: Isomorphism to depth \(n-1\) implies isomorphism to all depths

DOI10.1016/0166-218X(93)E0133-JzbMath0815.68074MaRDI QIDQ1343157

N. Norris

Publication date: 1 February 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

finite-state machinescomputer networksedge-labeled digraphs

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (23)

Quasifibrations of graphs to find symmetries and reconstruct biological networks ⋮ Comparing Universal Covers in Polynomial Time ⋮ Unfoldings and Coverings of Weighted Graphs ⋮ How to meet when you forget: log-space rendezvous in arbitrary graphs ⋮ Computing on anonymous networks with sense of direction ⋮ Mapping simple polygons: how robots benefit from looking back ⋮ Drawing maps with advice ⋮ Simple agents learn to find their way: an introduction on mapping polygons ⋮ Computing functions on asynchronous anonymous networks ⋮ Universal dynamic synchronous self-stabilization ⋮ How much memory is needed for leader election ⋮ Knowledge, level of symmetry, and time of leader election ⋮ Wang tilings and distributed verification on anonymous torus networks ⋮ THE SPACE COMPLEXITY OF LEADER ELECTION IN ANONYMOUS NETWORKS ⋮ Leader election for anonymous asynchronous agents in arbitrary networks ⋮ Comparing universal covers in polynomial time ⋮ Topology recognition and leader election in colored networks ⋮ Symmetries and sense of direction in labeled graphs ⋮ Approximate lumpability for Markovian agent-based models using local symmetries ⋮ Setting Ports in an Anonymous Network: How to Reduce the Level of Symmetry? ⋮ Computing on Anonymous Quantum Network ⋮ Graph fibrations, graph isomorphism, and PageRank ⋮ Distinguishing views in symmetric networks: a tight lower bound

Cites Work

• Easy impossibility proofs for distributed consensus problems
• Finite common coverings of graphs
• Computing on an anonymous ring
• Computing functions on asynchronous anonymous networks
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Universal covers of graphs: Isomorphism to depth \(n-1\) implies isomorphism to all depths