Interval routing schemes allow broadcasting with linear message-complexity

DOI10.1007/s004460100058zbMath1448.68045OpenAlexW2069153881MaRDI QIDQ5138363

Cyril Gavoille, Bernard Mans, Pierre Fraigniaud

Publication date: 3 December 2020

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

Full work available at URL: https://doi.org/10.1007/s004460100058

zbMATH Keywords

distributed computingcompact routingbroadcastinginterval routing

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed systems (68M14)

Related Items

Compact and localized distributed data structures ⋮ Setting port numbers for fast graph exploration

Cites Work

• Unnamed Item
• Unnamed Item
• On the impact of sense of direction on message complexity
• Designing networks with compact routing tables
• Methods and problems of communication in usual networks
• A survey on interval routing
• Sense of direction in distributed computing
• Memory requirement for routing in distributed networks
• Labelling and Implicit Routing in Networks
• A trade-off between information and communication in broadcast protocols
• The complexity of interval routing on random graphs
• A survey of gossiping and broadcasting in communication networks
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Worst Case Bounds for Shortest Path Interval Routing
• Sense of direction: Definitions, properties, and classes
• Lower bounds for compact routing
• Searching among intervals and compact routing tables
• The Compactness of Interval Routing
• A trade-off between space and efficiency for routing tables
• On Multi-Label Linear Interval Routing Schemes
• Interval routing schemes