Constructing disjoint paths on expander graphs
From MaRDI portal
Publication:1262782
DOI10.1007/BF02125897zbMath0686.68056MaRDI QIDQ1262782
Publication date: 1989
Published in: Combinatorica (Search for Journal in Brave)
complexityparallel algorithmsinterconnection networkdisjoint pathsDeterministic-\({\mathcal P}\)expander interconnection graphsparallel-distributed model of computationRandom-\({\mathcal N}{\mathcal C}\)
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (9)
Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs ⋮ On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks ⋮ The electrical resistance of a graph captures its commute and cover times ⋮ Shortest edge-disjoint paths in graphs ⋮ Expander graphs and their applications ⋮ The cover time of a regular expander is O(n log n) ⋮ Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing ⋮ Redundant multicast routing in multilayer networks with shared risk resource groups: complexity, models and algorithms ⋮ Approximations for the disjoint paths problem in high-diameter planar networks
Cites Work
- Unnamed Item
- Unnamed Item
- Graph minors. VI. Disjoint paths across a disc
- Expanding graphs contain all small trees
- Matching is as easy as matrix inversion
- Constructing a perfect matching is in random NC
- Eigenvalues and expanders
- Parallel hashing
- The Token Distribution Problem
- A Scheme for Fast Parallel Communication
This page was built for publication: Constructing disjoint paths on expander graphs
