[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/28395.28424acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article
Free access

Constructing disjoint paths on expander graphs

Published: 01 January 1987 Publication History

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.

References

[1]
M. AjtM, J. Komlos and E. Szemeredi, An O(nlogn) Sorting Network, 15th Syrup. on Theory of Computing, 1983, pp. 1-9.
[2]
R. Alehunas, Randomized Parallel Communication, 1st Syrup. on Principles of Distributed Computing, 1982, pp. 60-72.
[3]
N. Alon, Eigenvalues and Expanders, manuscript, 1985.
[4]
P. Feldman, J. Friedman and N. Pippenger, Non-Blocking Networks, 18th Syrup. on Theory of Compu ting, 1986, pp. 247-254.
[5]
J. Friedman and N. Pippenger, Expanding Graphs Contain All Small Trees, Report RJ 5145 (53485), IBM Almaden Research, May 1986.
[6]
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.
[7]
A.R. Karlin and E. Upfal, Parallel Hashing- an Efficient Implementation of Shared Memory, 18th Syrup. oa Theory of Computing, 1986, pp. 160-168.
[8]
R.M. Karp, E. Upfal and A. Wigderson, Constructing Perfect M a. tching is in Random-NC, Combinatorica 6, (1986), pp. 35-40.
[9]
E.L. Lawler, Combinatorial Optimization' Networks and Matroids, Holt, Rinehart and Winston. 1976.
[10]
A Lubotzky, R. Phillips and P. Sarnak, Ramanugan Conjecture and Explicit Constructions of Expanders, 18tb Syrup. on Theory of Computing, 1986, 2.10-246.
[11]
K. Mttlmuley, U.V. Va~ziralli and V.V. ~'azirani, Ma. tch{ng is as Easy as Matrix Inversion, Manuscript, 1985.
[12]
N. Pippenger, Parallel Communication with Bounded Buffers, 25th Syrup. on Foundations of Computer Science, 1984, 127-136.
[13]
D. Peleg and U. Upfal, The Token Distribution Problem, 27th Syrup. on Foundations of Computer Science, 1986, 418-427.
[14]
N. Robertson and P.D. Seymour, Graph Minors - XIII; Vertex- Disjoint Paths, Manuscript, 1986.
[15]
E. Senata, Non-negative Matrices and Markov Chains, Springer- Verlag, 1973.
[16]
E. Shamir and A. Schuster, Parallel Routing in Networks: Back to Circuit Switching?, Manuscript, 1986.
[17]
E. Upfal, Efficient Schemes for Parallel Communication, J. ACM 31, (1984), 507-517.
[18]
L. Valiant, A Scheme for Fast Parallel Communication, SLAM J. on Computing 11, (1982), 350-361.

Cited By

View all
  • (2024)New Structures and Algorithms for Length-Constrained Expander Decompositions2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00102(1634-1645)Online publication date: 27-Oct-2024
  • (2005)Expander properties in random regular graphs with edge faultsSTACS 9510.1007/3-540-59042-0_93(421-432)Online publication date: 1-Jun-2005
  • (2005)Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computingAutomata, Languages and Programming10.1007/3-540-58201-0_94(508-519)Online publication date: 29-May-2005
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computing
January 1987
471 pages
ISBN:0897912217
DOI:10.1145/28395
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1987

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

STOC87
Sponsor:

Acceptance Rates

STOC '87 Paper Acceptance Rate 50 of 165 submissions, 30%;
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25
57th Annual ACM Symposium on Theory of Computing (STOC 2025)
June 23 - 27, 2025
Prague , Czech Republic

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)65
  • Downloads (Last 6 weeks)7
Reflects downloads up to 22 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)New Structures and Algorithms for Length-Constrained Expander Decompositions2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00102(1634-1645)Online publication date: 27-Oct-2024
  • (2005)Expander properties in random regular graphs with edge faultsSTACS 9510.1007/3-540-59042-0_93(421-432)Online publication date: 1-Jun-2005
  • (2005)Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computingAutomata, Languages and Programming10.1007/3-540-58201-0_94(508-519)Online publication date: 29-May-2005
  • (2005)Nonblocking graphs: Greedy algorithms to compute disjoint pathsSTACS 9010.1007/3-540-52282-4_48(250-262)Online publication date: 6-Jun-2005
  • (2002)Network topology generatorsACM SIGCOMM Computer Communication Review10.1145/964725.63304032:4(147-159)Online publication date: 19-Aug-2002
  • (2002)Network topology generatorsProceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications10.1145/633025.633040(147-159)Online publication date: 19-Aug-2002
  • (1989)The electrical resistance of a graph captures its commute and cover timesProceedings of the twenty-first annual ACM symposium on Theory of computing10.1145/73007.73062(574-586)Online publication date: 1-Feb-1989
  • (1989)Shortest edge-disjoint paths in graphsSTACS 8910.1007/BFb0029011(505-516)Online publication date: 1989
  • (1988)Optimal parallel algorithm for the Hamiltonian cycle problem on dense graphsProceedings of the 29th Annual Symposium on Foundations of Computer Science10.1109/SFCS.1988.21936(186-193)Online publication date: 24-Oct-1988

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media