On the impact of sense of direction on message complexity

DOI10.1016/S0020-0190(97)00091-4zbMath1336.68197MaRDI QIDQ287123

Bernard Mans, Paola Flocchini, Nicola Santoro

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

complexitygraph algorithmsdistributed algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (12)

OPTIMAL CONSTRUCTION OF SENSE OF DIRECTION IN A TORUS BY A MOBILE AGENT ⋮ Memory Efficient Anonymous Graph Exploration ⋮ Computing on anonymous networks with sense of direction ⋮ Interval routing schemes allow broadcasting with linear message-complexity ⋮ Torus orientation ⋮ Lower bounds for sense of direction in regular graphs ⋮ Rapid almost-complete broadcasting in faulty networks ⋮ Symmetries and sense of direction in labeled graphs ⋮ A survey on interval routing ⋮ TOPOLOGICAL CONSTRAINTS FOR SENSE OF DIRECTION ⋮ Coverings that preserve sense of direction ⋮ Sense of direction in distributed computing

Cites Work

• A fully distributed (minimal) spanning tree algorithm
• Towards optimal distributed election on chordal rings
• Efficient elections in chordal ring networks
• Corrigenda: Corrections to a distributed depth-first search algorithm
• On the message complexity of distributed problems
• Graph Traversal Techniques and the Maximum Flow Problem in Distributed Computation
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• An improved election algorithm in chordal ring networks
• Leader election in complete networks

This page was built for publication: On the impact of sense of direction on message complexity