D. Peleg
ABSTRACT
In a typical parallel or distributed computation model processors are connected by a sparse interconnection network. To establish open-line communication between pairs of processors that wish to communicate interactively, a set of disjoint paths has to be constructed on the network. Since communication needs vary in time, paths have to be dynamically constructed and destroyed.
We study the complexity of constructing disjoint paths between given pairs of vertices on expander interconnection graphs. These graphs have been shown before to possess desirable properties for other communication tasks.
We present a sufficient condition for the existence of Κ ≤ np edge-disjoint paths connecting any set of Κ pairs of vertices on an expander graph. We then show that the computational problem of constructing these paths lies in the classes Deterministic-P and Random-NC.
Furthermore, we show that the set of paths can be constructed in probabilistic polylog time in the parallel-distributed model of computation, in which the n participating processors reside in the nodes of the communication graph and all communication is done through edges of the graph. Thus, the disjoint paths are constructed in the very computation model that uses them.
Finally, we show how to apply variants of our parallel algorithms to find sets of vertex-disjoint paths when certain conditions are satisfied.
- AKS.M. AjtM, J. Komlos and E. Szemeredi, An O(nlogn) Sorting Network, 15th Syrup. on Theory of Computing, 1983, pp. 1-9. Google Scholar
Digital Library
- A.R. Alehunas, Randomized Parallel Communication, 1st Syrup. on Principles of Distributed Computing, 1982, pp. 60-72. Google ScholarDigital Library
- Al.N. Alon, Eigenvalues and Expanders, manuscript, 1985.Google Scholar
- FFP.P. Feldman, J. Friedman and N. Pippenger, Non-Blocking Networks, 18th Syrup. on Theory of Compu ting, 1986, pp. 247-254. Google ScholarDigital Library
- FP.J. Friedman and N. Pippenger, Expanding Graphs Contain All Small Trees, Report RJ 5145 (53485), IBM Almaden Research, May 1986.Google Scholar
- GJ.M.R. Garey and D.S. Johnson, Computers and Intractability; a Guide to the Theory ot' NP- Completeness, W.H. FreeIna. n and Co., San-Francisco, 1979. Google ScholarDigital Library
- KU.A.R. Karlin and E. Upfal, Parallel Hashing- an Efficient Implementation of Shared Memory, 18th Syrup. oa Theory of Computing, 1986, pp. 160-168. Google ScholarDigital Library
- KUW.R.M. Karp, E. Upfal and A. Wigderson, Constructing Perfect M a. tching is in Random-NC, Combinatorica 6, (1986), pp. 35-40. Google ScholarDigital Library
- L.E.L. Lawler, Combinatorial Optimization' Networks and Matroids, Holt, Rinehart and Winston. 1976.Google Scholar
- LPS.A Lubotzky, R. Phillips and P. Sarnak, Ramanugan Conjecture and Explicit Constructions of Expanders, 18tb Syrup. on Theory of Computing, 1986, 2.10-246. Google ScholarDigital Library
- MVV.K. Mttlmuley, U.V. Va~ziralli and V.V. ~'azirani, Ma. tch{ng is as Easy as Matrix Inversion, Manuscript, 1985.Google Scholar
- P.N. Pippenger, Parallel Communication with Bounded Buffers, 25th Syrup. on Foundations of Computer Science, 1984, 127-136.Google Scholar
- PU.D. Peleg and U. Upfal, The Token Distribution Problem, 27th Syrup. on Foundations of Computer Science, 1986, 418-427.Google ScholarDigital Library
- RS.N. Robertson and P.D. Seymour, Graph Minors - XIII; Vertex- Disjoint Paths, Manuscript, 1986.Google Scholar
- S.E. Senata, Non-negative Matrices and Markov Chains, Springer- Verlag, 1973.Google Scholar
- SS.E. Shamir and A. Schuster, Parallel Routing in Networks: Back to Circuit Switching?, Manuscript, 1986.Google Scholar
- U.E. Upfal, Efficient Schemes for Parallel Communication, J. ACM 31, (1984), 507-517. Google ScholarDigital Library
- V.L. Valiant, A Scheme for Fast Parallel Communication, SLAM J. on Computing 11, (1982), 350-361.Google ScholarCross Ref
Index Terms
- Constructing disjoint paths on expander graphs
Recommendations
Edge-Disjoint Paths in Expander Graphs
Given a graph G=(V,E)and a set of $\kappa$ pairs of vertices in V, we are interested in finding, for each pair (ai, bi), a path connecting ai to bi such that the set of $\kappa$ paths so found is edge-disjoint. For arbitrary graphs the problem is ${\...
On shortest disjoint paths in planar graphs
For a graph G and a collection of vertex pairs {(s"1,t"1),...,(s"k,t"k)}, the k disjoint paths problem is to find k vertex-disjoint paths P"1,...,P"k, where P"i is a path from s"i to t"i for each i=1,...,k. In the corresponding optimization problem, the ...
On Shortest Disjoint Paths in Planar Graphs
ISAAC '09: Proceedings of the 20th International Symposium on Algorithms and ComputationFor a graph and a set of vertex pairs {(s 1, t 1), ..., (s k , t k )}, the k disjoint paths problem is to find k vertex-disjoint paths P 1, ..., P k , where P i is a path from s i to t i for each i = 1, ..., k. In the corresponding ...
Comments