Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs

DOI10.1017/S0963548300004284MaRDI QIDQ4500422zbMATH OpenOpenAlexWikidataFDO

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

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)

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

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)