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

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

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

(10)

• A lower bound of the expected maximum number of edge-disjoint \(s\)--\(t\) paths on probabilistic graphs
• scientific article; zbMATH DE number 1003293 (Why is no real title available?)
• Shortest node-disjoint paths on random graphs
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• scientific article; zbMATH DE number 1305424 (Why is no real title available?)
• Communication lower bounds via critical block sensitivity
• Extension complexity of independent set polytopes
• Edge-disjoint paths in expanders: online with removals
• Lower bounds on the complexity of mixed-integer programs for stable set and knapsack
• Lower bounds on the complexity of mixed-integer programs for stable set and knapsack

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)