Name
Abstract | ||
|---|---|---|
Given a digraph D=(V,A) and a set of $\kappa$ pairs of vertices in V, we are interested in finding, for each pair (xi, yi), a directed path connecting xi to yi such that the set of $\kappa$ paths so found is arc-disjoint. For arbitrary graphs the problem is ${\cal NP}$-complete, even for $\kappa=2$. We present a polynomial time randomized algorithm for finding arc-disjoint paths in an r-regular expander digraph D. We show that if D has sufficiently strong expansion properties and the degree r is sufficiently large, then all sets of $\kappa=\Omega(n/\log n)$ pairs of vertices can be joined. This is within a constant factor of best possible. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1137/S0097539701398582 | foundations of computer science |
Keywords | DocType | Volume |
cal np,constant factor,k pair,strong expansion propertiesand r,k path,arc-disjoint path,arbitrary graph,log n,randomized algorithm,digraph d,arc-disjoint paths,strong expansion property,polynomial time,expander digraphs,degree r,set theory,computational complexity,directed graphs | Conference | 32 |
Issue | ISSN | ISBN |
2 | 0097-5397 | 0-7695-1390-5 |
Citations | PageRank | References |
2 | 0.45 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tom Bohman | 1 | 250 | 33.01 |
| Alan M. Frieze | 2 | 4837 | 787.00 |