Direct routing: Algorithms and complexity

DOI10.1007/s00453-005-1189-3zbMath1117.68087OpenAlexW2105063585MaRDI QIDQ2369874

Malik Magdon-Ismail, Costas Busch, Marios Mavronicolas, Paul G. Spirakis

Publication date: 21 June 2007

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-005-1189-3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Communication networks in operations research (90B18) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Related Items (3)

The network as a storage device: dynamic routing with bounded buffers ⋮ Universal Packet Routing with Arbitrary Bandwidths and Transit Times ⋮ Bounding Residence Times for Atomic Dynamic Routings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Routing on trees
• Zero knowledge and the chromatic number
• Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
• Potential function analysis of greedy hot-potato routing
• Many-to-many routing on trees via matchings
• A lower bound for nearly minimal adaptive and hot potato algorithms
• Time-constrained scheduling of weighted packets on trees and meshes
• Scheduling time-constrained communication in linear networks
• Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules
• Hard-Potato routing
• A Scheme for Fast Parallel Communication
• Shortest-Path Routing in Arbitrary Networks
• Routing Permutations on Graphs via Matchings
• Optimal Oblivious Path Selection on the Mesh
• Algorithms – ESA 2004

This page was built for publication: Direct routing: Algorithms and complexity