Oblivious routing on node-capacitated and directed graphs.

Mohammad Taghi Hajiaghayi Robert D. Kleinberg Tom Leighton Harald Räcke

Published in: SODA (2005)

Keyphrases

directed graph
routing problem
source node
random walk
undirected graph
shortest path problem
single source

vehicle routing problem
graph structure
lot sizing
directed acyclic graph
np hard
strongly connected

routing algorithm
shortest path
disjoint paths
network design problem
maximum flow
network topology

ad hoc networks
multi item
web graph
edge weights
special case
destination node