Direct routing: Algorithms and complexity
DOI10.1007/S00453-005-1189-3zbMATH Open1117.68087OpenAlexW2105063585MaRDI QIDQ2369874FDOQ2369874
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
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
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)
Cites Work
- Title not available (Why is that?)
- Approximation algorithms for NP-hard problems.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Zero knowledge and the chromatic number
- Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
- Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules
- Routing Permutations on Graphs via Matchings
- Title not available (Why is that?)
- Shortest-Path Routing in Arbitrary Networks
- A Scheme for Fast Parallel Communication
- Time-constrained scheduling of weighted packets on trees and meshes
- Scheduling time-constrained communication in linear networks
- Many-to-many routing on trees via matchings
- Title not available (Why is that?)
- Routing on trees
- Title not available (Why is that?)
- Title not available (Why is that?)
- A lower bound for nearly minimal adaptive and hot potato algorithms
- Potential function analysis of greedy hot-potato routing
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Algorithms – ESA 2004
- Optimal Oblivious Path Selection on the Mesh
- Hard-potato routing
Cited In (12)
- 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
- Title not available (Why is that?)
- Efficient bufferless packet switching on trees and leveled networks
- Directional Routing via Generalized st-Numberings
- Approximation and Online Algorithms
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)
