A lower bound for nearly minimal adaptive and hot potato algorithms

DOI10.1007/3-540-61680-2_76zbMATH Open1379.68377OpenAlexW1544785026MaRDI QIDQ4595508FDOQ4595508

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

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

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)

Cited In (5)

• A New Bound for Pure Greedy Hot Potato Routing
• Nonmonotonic phenomena in packet routing
• Lower Bounds for One-to-one Packet Routing on Trees using Hot-Potato Algorithms
• On minimizing the number of ADMs--tight bounds for an algorithm without preprocessing
• Title not available (Why is that?)

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)