A lower bound for nearly minimal adaptive and hot potato algorithms

DOI10.1007/3-540-61680-2_76MaRDI QIDQ4595508zbMATHOpenAlexFDO

Authors Donald D. Chinn, Assaf Schuster, Ishai Ben-Aroya

Publication date 5 December 2017

Published in Algorithms — ESA '96 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61680-2_76

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Network design and communication in computer systems (68M10) Network protocols (68M12)

Recommendations

• A lower bound for nearly minimal adaptive and hot potato algorithms
• Potential function analysis of greedy hot-potato routing
• Greedy hot-potato routing on the two-dimensional mesh
• scientific article; zbMATH DE number 1256693
• Deterministic Hot-Potato Permutation Routing on the Mesh and the Torus

Cited in

(5)

• Nonmonotonic phenomena in packet routing
• A New Bound for Pure Greedy Hot Potato Routing
• Lower Bounds for One-to-one Packet Routing on Trees using Hot-Potato Algorithms
• scientific article; zbMATH DE number 1555950 (Why is no real title available?)
• On minimizing the number of ADMs--tight bounds for an algorithm without preprocessing

This page was built for publication: A lower bound for nearly minimal adaptive and hot potato algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4595508)