Optimal Construction of Edge-Disjoint Paths in Random Graphs
From MaRDI portal
Paths and cycles (05C38) Connectivity (05C40) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Sums of independent random variables; random walks (60G50) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Deterministic network models in operations research (90B10) Communication networks in operations research (90B18)
Recommendations
Cites work
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- A theorem on flows in networks
- An Exact Sublinear Algorithm for the Max-Flow, Vertex Disjoint Paths and Communication Problems on Random Graphs
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Existence and Construction of Edge-Disjoint Paths on Expander Graphs
- Graph minors. XIII: The disjoint paths problem
- scientific article; zbMATH DE number 3492718 (Why is no real title available?)
- scientific article; zbMATH DE number 1263178 (Why is no real title available?)
- The Token Distribution Problem
Cited in
(46)- Vertex percolation on expander graphs
- Random regular graphs of non-constant degree: concentration of the chromatic number
- Constructing disjoint paths on expander graphs
- Random groups, random graphs and eigenvalues of p-Laplacians
- A forest building process on simple graphs
- The spectral gap of dense random regular graphs
- Size biased couplings and the spectral gap for random regular graphs
- New algorithms for maximum disjoint paths based on tree-likeness
- A lower bound of the expected maximum number of edge-disjoint \(s\)--\(t\) paths on probabilistic graphs
- Reliable communication over highly connected noisy networks
- The spectral gap of sparse random digraphs
- Sparse random tensors: concentration, regularization and applications
- Exchangeable pairs, switchings, and random regular graphs
- Edge-disjoint paths in expander graphs
- Graphs with many strong orientations
- Discrepancy properties for random regular digraphs
- Local resilience and hamiltonicity maker-breaker games in random regular graphs
- scientific article; zbMATH DE number 1003293 (Why is no real title available?)
- scientific article; zbMATH DE number 3883622 (Why is no real title available?)
- Shortest node-disjoint paths on random graphs
- Functional limit theorems for random regular graphs
- scientific article; zbMATH DE number 1305424 (Why is no real title available?)
- Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs
- Arc-Disjoint Paths in Expander Digraphs
- scientific article; zbMATH DE number 871922 (Why is no real title available?)
- scientific article; zbMATH DE number 1445370 (Why is no real title available?)
- Complete Minors in Graphs Without Sparse Cuts
- Sherali-adams strikes back
- Almost polynomial hardness of node-disjoint paths in grids
- Sherali-Adams strikes back
- Randomized rumour spreading: the effect of the network topology
- Structure of eigenvectors of random regular digraphs
- Spectra of lifted Ramanujan graphs
- Constructing disjoint paths for secure communication
- 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
- Spectral gap and edge universality of dense random regular graphs
- Edge-disjoint paths in expanders: online with removals
- A spectral bound on hypergraph discrepancy
- Minors in small-set expanders
- A note on quantum expanders
- Rumors with changing credibility
- Clique factors in pseudorandom graphs
- Vertex-separating path systems in random 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)
