Optimal Construction of Edge-Disjoint Paths in Random Graphs

DOI10.1137/S0097539795290805zbMath0912.05058MaRDI QIDQ4210165

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

Publication date: 21 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

eigenvaluesrandom graphedge-disjoint pathspolynomial-time randomized algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Sums of independent random variables; random walks (60G50) Communication networks in operations research (90B18) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Paths and cycles (05C38) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items

Random groups, random graphs and eigenvalues of \(p\)-Laplacians, Complete Minors in Graphs Without Sparse Cuts, Functional limit theorems for random regular graphs, A forest building process on simple graphs, Discrepancy properties for random regular digraphs, Random walk hitting times and effective resistance in sparsely connected Erdős‐Rényi random graphs, The spectral gap of random regular graphs, Global eigenvalue fluctuations of random biregular bipartite graphs, On the second eigenvalue of random bipartite biregular graphs, Randomized Rumour Spreading: The Effect of the Network Topology, Structure of eigenvectors of random regular digraphs, The spectral gap of dense random regular graphs, Size biased couplings and the spectral gap for random regular graphs, Exchangeable pairs, switchings, and random regular graphs, Reliable communication over highly connected noisy networks, Spectra of lifted Ramanujan graphs, New algorithms for maximum disjoint paths based on tree-likeness, Vertex percolation on expander graphs, The spectral gap of sparse random digraphs, Sparse random tensors: concentration, regularization and applications, Local Resilience and Hamiltonicity Maker–Breaker Games in Random Regular Graphs, Graphs with Many Strong Orientations, Sherali-adams strikes back, Random regular graphs of non-constant degree: concentration of the chromatic number, Unnamed Item, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• A theorem on flows in networks
• Approximate counting, uniform generation and rapidly mixing Markov chains
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Graph minors. XIII: The disjoint paths problem
• The Token Distribution Problem
• An Exact Sublinear Algorithm for the Max-Flow, Vertex Disjoint Paths and Communication Problems on Random Graphs
• Existence and Construction of Edge-Disjoint Paths on Expander Graphs