Optimal Construction of Edge-Disjoint Paths in Random Graphs.

Andrei Z. Broder Alan M. Frieze Stephen Suen Eli Upfal

Published in: SIAM J. Comput. (1998)

Keyphrases

disjoint paths
random graphs
undirected graph
approximation algorithms
minimum cost
directed graph
worst case
spanning tree
learning curves
optimal solution
phase transition
lower bound
data structure
dynamic programming
connected components
graph structure
special case