Lower bounds for sense of direction in regular graphs

DOI10.1007/s00446-003-0092-xzbMath1448.68354OpenAlexW1988913321MaRDI QIDQ5138498

Paolo Boldi, Sebastiano Vigna

Publication date: 4 December 2020

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-003-0092-x

zbMATH Keywords

random graphsregular graphsdistributed computingsense of direction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Distributed systems (68M14) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the impact of sense of direction on message complexity
• Asymptotic enumeration by degree sequence of graphs of high degree
• Lower bounds for weak sense of direction
• Sense of direction in distributed computing
• Random regular graphs of high degree
• Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity
• Sense of direction: Definitions, properties, and classes
• Complexity of Deciding Sense of Direction

This page was built for publication: Lower bounds for sense of direction in regular graphs