Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs.
Matthew AndrewsJulia ChuzhoyVenkatesan GuruswamiSanjeev KhannaKunal TalwarLisa ZhangPublished in: Electron. Colloquium Comput. Complex. (2007)
Keyphrases
- disjoint paths
- approximation algorithms
- undirected graph
- dynamic routing
- minimum cost
- np hard
- special case
- directed graph
- packet transmission
- worst case
- graph structure
- network topology
- packet loss
- random graphs
- directed acyclic graph
- connected components
- complex networks
- mobile ad hoc networks
- multi dimensional
- reinforcement learning