Optimal Construction of Edge-Disjoint Paths in Random Graphs
DOI10.1137/S0097539795290805zbMATH Open0912.05058MaRDI QIDQ4210165FDOQ4210165
Alan Frieze, Andrei Broder, Stephen Suen, Eli Upfal
Publication date: 21 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Sums of independent random variables; random walks (60G50) Paths and cycles (05C38) Connectivity (05C40) Parallel algorithms in computer science (68W10) Communication networks in operations research (90B18)
Cites Work
- A theorem on flows in networks
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- Graph minors. XIII: The disjoint paths problem
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Title not available (Why is that?)
- The Token Distribution Problem
- Title not available (Why is that?)
- Existence and Construction of Edge-Disjoint Paths on Expander Graphs
- An Exact Sublinear Algorithm for the Max-Flow, Vertex Disjoint Paths and Communication Problems on Random Graphs
Cited In (34)
- The spectral gap of sparse random digraphs
- Structure of eigenvectors of random regular digraphs
- Sherali-adams strikes back
- Title not available (Why is that?)
- The spectral gap of dense random regular graphs
- Local Resilience and Hamiltonicity Maker–Breaker Games in Random Regular Graphs
- Spectral gap and edge universality of dense random regular graphs
- Reliable communication over highly connected noisy networks
- Random groups, random graphs and eigenvalues of \(p\)-Laplacians
- Exchangeable pairs, switchings, and random regular graphs
- Random walk hitting times and effective resistance in sparsely connected Erdős‐Rényi random graphs
- Vertex percolation on expander graphs
- Discrepancy properties for random regular digraphs
- Constructing disjoint paths for secure communication
- New algorithms for maximum disjoint paths based on tree-likeness
- Edge-disjoint paths in expander graphs
- Sparse random tensors: concentration, regularization and applications
- Title not available (Why is that?)
- Graphs with many strong orientations
- Global eigenvalue fluctuations of random biregular bipartite graphs
- Arc-Disjoint Paths in Expander Digraphs
- On the second eigenvalue of random bipartite biregular graphs
- Random regular graphs of non-constant degree: concentration of the chromatic number
- Complete Minors in Graphs Without Sparse Cuts
- A forest building process on simple graphs
- Title not available (Why is that?)
- Constructing disjoint paths on expander graphs
- Title not available (Why is that?)
- Functional limit theorems for random regular graphs
- Spectra of lifted Ramanujan graphs
- Size biased couplings and the spectral gap for random regular graphs
- A lower bound of the expected maximum number of edge-disjoint \(s\)--\(t\) paths on probabilistic graphs
- Randomized Rumour Spreading: The Effect of the Network Topology
- The spectral gap of random regular graphs
This page was built for publication: Optimal Construction of Edge-Disjoint Paths in Random Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210165)
