Loading...
Please wait, while we are loading the content...
Similar Documents
Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs
| Content Provider | Scilit |
|---|---|
| Author | Frieze, Alan M. Zhao, Lei |
| Copyright Year | 2000 |
| Description | Given a graph G = (V, E) and a set of κ pairs of vertices in V, we are interested in finding, for each pair $(a_{i}$, $b_{i}$), a path connecting $a_{i}$ to $b_{i}$ such that the set of κ paths so found is edge-disjoint. (For arbitrary graphs the problem is [Nscr ][Pscr ]-complete, although it is in [Pscr ] if κ is fixed.)We present a polynomial time randomized algorithm for finding edge-disjoint paths in the random regular graph $G_{n,r}$, for sufficiently large r. (The graph is chosen first, then an adversary chooses the pairs of end-points.) We show that almost every $G_{n,r}$ is such that all sets of κ = Ω(n/log n) pairs of vertices can be joined. This is within a constant factor of the optimum. |
| Related Links | http://www.aladdin.cs.cmu.edu/papers/pdfs/y2000/regpath.pdf https://www.cambridge.org/core/services/aop-cambridge-core/content/view/BEC3157FBB1D04AD273EA914491791AC/S0963548300004284a.pdf/div-class-title-optimal-construction-of-edge-disjoint-paths-in-random-regular-graphs-div.pdf |
| Ending Page | 263 |
| Page Count | 23 |
| Starting Page | 241 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s0963548300004284 |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 3 |
| Volume Number | 9 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2000-05-01 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing Random Regular Graph Optimal Construction disjoint Path Randomized Algorithm |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
