Direct routing: Algorithms and complexity

DOI10.1007/S00453-005-1189-3MaRDI QIDQ2369874zbMATH OpenOpenAlexFDO

Authors Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas, P. 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) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Communication networks in operations research (90B18) Network design and communication in computer systems (68M10)

Recommendations

• Algorithms – ESA 2004
• Packet Routing: Complexity and Algorithms
• Compact roundtrip routing in directed networks
• scientific article; zbMATH DE number 1303574
• The complexity of rerouting shortest paths
• The complexity of rerouting shortest paths
• On the computational complexity of continuous routing
• scientific article; zbMATH DE number 1538069
• Compact roundtrip routing in directed networks (extended abstract)
• scientific article; zbMATH DE number 1568938

Cites work

• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256693 (Why is no real title available?)
• scientific article; zbMATH DE number 1256752 (Why is no real title available?)
• scientific article; zbMATH DE number 1256753 (Why is no real title available?)
• scientific article; zbMATH DE number 1256754 (Why is no real title available?)
• scientific article; zbMATH DE number 1303574 (Why is no real title available?)
• scientific article; zbMATH DE number 1559580 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 6472620 (Why is no real title available?)
• A Scheme for Fast Parallel Communication
• A lower bound for nearly minimal adaptive and hot potato algorithms
• Algorithms – ESA 2004
• Approximation algorithms for NP-hard problems.
• Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules
• Hard-potato routing
• Many-to-many routing on trees via matchings
• Optimal Oblivious Path Selection on the Mesh
• Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
• Potential function analysis of greedy hot-potato routing
• Routing Permutations on Graphs via Matchings
• Routing on trees
• Scheduling time-constrained communication in linear networks
• Shortest-Path Routing in Arbitrary Networks
• Time-constrained scheduling of weighted packets on trees and meshes
• Zero knowledge and the chromatic number

Cited in

(12)

• Approximation and Online Algorithms
• Packet Routing: Complexity and Algorithms
• The non-stop disjoint trajectories problem
• Algorithms – ESA 2004
• Bounding Residence Times for Atomic Dynamic Routings
• The network as a storage device: dynamic routing with bounded buffers
• Direct \(k\)-routing versus cross-docking: worst-case results
• Universal packet routing with arbitrary bandwidths and transit times
• Nonmonotonic phenomena in packet routing
• scientific article; zbMATH DE number 2170448 (Why is no real title available?)
• Efficient bufferless packet switching on trees and leveled networks
• Directional Routing via Generalized st-Numberings

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

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