A lower bound for nearly minimal adaptive and hot potato algorithms

DOI10.1007/PL00009219MaRDI QIDQ1393080zbMATH OpenOpenAlexFDO

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

Publication date 10 November 1998

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

hot potato routingpermutation routing algorithms

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Recommendations

• A lower bound for nearly minimal adaptive and hot potato algorithms
• 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
• scientific article; zbMATH DE number 1445335

Cited in

(12)

• Potential function analysis of greedy hot-potato routing
• Many-to-many routing on trees via matchings
• Direct routing: Algorithms and complexity
• Nonmonotonic phenomena in packet routing
• Lower Bounds for One-to-one Packet Routing on Trees using Hot-Potato Algorithms
• A New Bound for Pure Greedy Hot Potato Routing
• scientific article; zbMATH DE number 1555950 (Why is no real title available?)
• A lower bound for nearly minimal adaptive and hot potato algorithms
• Greedy hot-potato routing on the two-dimensional mesh
• Networks on which hot-potato routing does not livelock
• \(\widetilde{O}\) (congestion + dilation) hot-potato routing on leveled networks
• 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 Q1393080)