Networks on which hot-potato routing does not livelock

DOI10.1007/s004460050005zbMath1448.68042OpenAlexW2046426181MaRDI QIDQ5137895

Robert Krauthgamer, Uriel Feige

Publication date: 3 December 2020

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

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

zbMATH Keywords

chordal graphstree networkslivelockhot-potato packet routing

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Distributed systems (68M14) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• Unnamed Item
• Bounds on evacuation time for deflection routing
• Treewidth. Computations and approximations
• Potential function analysis of greedy hot-potato routing
• A lower bound for nearly minimal adaptive and hot potato algorithms
• Randomized Single-Target Hot-Potato Routing
• Nonuniform traffic in the Manhattan street network
• Greedy Packet Scheduling on Shortest Paths
• Greedy hot-potato routing on the two-dimensional mesh
• Fast deflection routing for packets and worms

This page was built for publication: Networks on which hot-potato routing does not livelock