Existence and Construction of Edge-Disjoint Paths on Expander Graphs
From MaRDI portal
Publication:4312418
DOI10.1137/S0097539792232021zbMath0808.05087WikidataQ57401575 ScholiaQ57401575MaRDI QIDQ4312418
Andrei Z. Broder, Eli Upfal, Alan M. Frieze
Publication date: 9 March 1995
Published in: SIAM Journal on Computing (Search for Journal in Brave)
60G50: Sums of independent random variables; random walks
90B18: Communication networks in operations research
68R10: Graph theory (including graph drawing) in computer science
90B10: Deterministic network models in operations research
05C38: Paths and cycles
68W10: Parallel algorithms in computer science
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Unnamed Item, Unnamed Item, Using mixture models for collaborative filtering, Highly symmetric expanders, New algorithms for maximum disjoint paths based on tree-likeness, Reliable communication over highly connected noisy networks, On certain connectivity properties of the internet topology, Routing in Undirected Graphs with Constant Congestion, Sparsifying Congested Cliques and Core-Periphery Networks, Graphs, Vectors, and Matrices, Optimal Construction of Edge-Disjoint Paths in Random Graphs