Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs

DOI10.1017/S0963548300004284zbMATH Open0953.05069OpenAlexW2020270524WikidataQ57401539 ScholiaQ57401539MaRDI QIDQ4500422FDOQ4500422

Authors: Lei Zhao, Alan Frieze 

Publication date: 23 January 2001

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548300004284

Recommendations

• scientific article; zbMATH DE number 1305424
• scientific article; zbMATH DE number 1003293
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• Edge-disjoint paths in expander graphs

zbMATH Keywords

edge-disjoint pathsrandom regular graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05) Paths and cycles (05C38)

Cited In (4)

• Shortest node-disjoint paths on random graphs
• Extension complexity of independent set polytopes
• A lower bound of the expected maximum number of edge-disjoint \(s\)--\(t\) paths on probabilistic graphs
• Communication lower bounds via critical block sensitivity

This page was built for publication: Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4500422)