A. Goldberg
ABSTRACT
We describe efficient deterministic techniques for breaking symmetry in parallel. The techniques work well on rooted trees and graphs of constant degree or genus. Our primary technique allows us to 3-color a rooted tree in Ο(lg*n) time on an EREW PRAM using a linear number of processors. We apply these techniques to construct fast linear processor algorithms for several problems, including (Δ + 1)-coloring constant-degree graphs, 5-coloring planar graphs, and finding depth-first-search trees in planar graphs. We also prove lower bounds for 2-coloring directed lists and for finding maximal independent sets in arbitrary graphs.
- 1.B. Awerbuch. Complexity of network synchronization. Journal of the Association for Computing Machinery, 32(4):804-823, October 1985. Google Scholar
Digital Library
- 2.B. A werbuch. A tight lower bound on tile time of distributed maximal independent set algorithms. February 1987. Unpublished manuscript.Google Scholar
- 3.B. Awerbuch, A. Israeli, and Y. Shiloach. Finding euler circuits in logarithmic parallel time. In Proc. l t~th A CM Syrup. on Theory of Computing, pages 249-257, 1984. Google ScholarDigital Library
- 4.P. Beame. Lower Bounds in Parallel Machine Computation. PhD thesis, University of Toronto, 1986. Google ScholarDigital Library
- 5.P. Beame and J. Hastad. Optimal bounds for decision problems on the CRCW P RAM. In Proc. 191h ACM Syrup. on Theory of Computing, 1987. (To appear). Google ScholarDigital Library
- 6.A. Borodin and J. E. Hopcroft. Routing, merging, and sorting on parallel models of computation. Journal of Computer and System Sciences, 30:130-145, 1985. Google ScholarDigital Library
- 7.J. Boyar and It. Karloff. Coloring planar graphs in parallel. 1986. Unpublished Manuscript.Google Scholar
- 8.N. Chiba, T. Nishizeki, and N. Saito. A linear 5-color algorithm of planar graphs. Journal of Algorithms, 2:317-327, 1981.Google ScholarCross Ref
- 9.R. Cole and U. Vishkin. Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. In Proc. 18th A (TM ,.qymp. on Theory of Computing, pages 206-219, 1986. Google ScholarDigital Library
- 10.S. Fortune and J. Wy!lie. Parallelism in random access machines. In Proc. l OtJt A CM Syrup. on Theory of Computing, pages 114-118, 1978. Google ScholarDigital Library
- 11.M. Furst, J. Saxe, and M. Sipser. Parity, circuits, and the polynomial tirae hierarchy. In Proc. 2~nd IEEE Conf on Foundations of Computer Science, pages 260-270, 1981.Google Scholar
- 12.R. G. Gallager, P. A. Humblet, and P. M Spira. A distributed algorithm for minimumweight spanning trees. A CM Transactions on Programming Languages and Systems, 5(1):66- 77, january 1983. Google ScholarDigital Library
- 13.A. Goldberg and S. Plotkin. E. Oqcient .Parallel Algorithms for (A + 1)-Coloring and Maximal Independent Set Problems. Technical Report MIT/LCS/TM-320, MIT, January lC~87.Google Scholar
- 14.A. Goldberg and S. rlotkin. Parallel (A + 1) coloring of constant-degree graphs. Information Processing Letters, 1986. Accepted for publication. Google ScholarDigital Library
- 15.A. V. Goldberg. Efficient Graph Algorithms for Sequential and Parallel Uomputers. PhD thesis, M.I.T., 1987.Google Scholar
- 16.M. Goldberg and T. Spencer. A new parallel algorithm for the maximal independent set problem. 1986. Submitted for publication.Google Scholar
- 17.F. Harary. Graph Theory. Addison-Wesley, 1972.Google Scholar
- 18.A. Israeli and Y. Shiloach. An i{mproved parallel algorithm for maximal matching. Information Processing Letters, 22:57-60, January 1986. Google ScholarDigital Library
- 19.R. M. Karp and A. Wigderson. A fast parallel algorithm for the maximal independent set problem, in Proc. 16th A CM Syrup. on Theory of Computing, pages 266-272, 1984. Google ScholarDigital Library
- 20.P. Klein and g. Reif. An efficient parallel algorithm for planarity. In Proc. of the 27th Annual Symposium on Foundations of Computer Science, pages 465-477, 1986.Google ScholarDigital Library
- 21.C. Leiserson and B. Maggs. Communicationefficient parallel graph algorithms. In Proc. of International Conference o~ Parallel Processing, pages 861-868, 1986.Google Scholar
- 22.C. Leiserson and C. Phillips. A fast parallel algorithm for region labeling. October 1986. (Extended abstract.).Google Scholar
- 23.N. Linial. Locality as an obstacle to distributed computing. February 1987. Unpublished manuscript.Google Scholar
- 24.M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM Joarhal of Comp., 15(4):1036-1052, November 1986. Google ScholarDigital Library
- 25.M. Luby. A simple parallel algorithm for the maxima! independent set problem. In Proc. 17th ACM Sym,. on Theory of Computing, pages 1- 10, 1985. Google ScholarDigital Library
- 26.D. Matula, Y. Shiloach, and R. Tarjan. Two Linear. time Algorithms for Five-coloring a Planar Graph. Technical Report STAN-CS-80-830, Department of Computer Science, Stanford University, Palo Alto, California, November 1980. Google ScholarDigital Library
- 27.G. Miller and J. Reif. Parallel tree contraction and its application. In Proc. of 26'~h Annual Symposium on Foundations of Computer Science, pages 478-489, October 1985.Google ScholarDigital Library
- 28.J. Naor. Two Parallel Algorithms in Graph Theory. Technical Report CS-86-6, Department of Computer Science, The Hebrew University of Jerusalem, Jerusalem, Israel, June 1986.Google Scholar
- 29.G. Shannon. Reduction techniques for designing linear-processor parallel algorithms on sparse graphs. 1986. (Extended Abstract).Google Scholar
- 30.J. Smith. Parallel algorithms for depth-first searches I. planar graphs. SIAM Journal on Computing, 15(3):814-830, August 1986. Google ScholarDigital Library
Index Terms
- Parallel symmetry-breaking in sparse graphs
Recommendations
The Locality of Distributed Symmetry Breaking
Symmetry-breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this article we work in the LOCAL model (where the input graph and underlying ...
Deterministic Massively Parallel Symmetry Breaking for Sparse Graphs
SPAA '23: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and ArchitecturesWe consider the problem of designing deterministic graph algorithms for the model of Massively Parallel Computation (MPC) that improve with the sparsity of the input graph, as measured by the standard notion of arboricity. For the problems of maximal ...
Sparse Kneser graphs are Hamiltonian
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of ComputingFor integers k≥1 and n≥2k+1, the Kneser graph K(n,k) is the graph whose vertices are the k-element subsets of {1,…,n} and whose edges connect pairs of subsets that are disjoint. The Kneser graphs of the form K(2k+1,k) are also known as the odd graphs. ...
Comments