Parallel symmetry-breaking in sparse graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel symmetry-breaking in sparse graphs

Full text

Pdf (1.06 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the nineteenth annual ACM symposium on Theory of computing table of contents

New York, New York, United States

Pages: 315 - 324

Year of Publication: 1987

ISBN:0-89791-221-7

Authors

A. Goldberg	Lab. for Computer Scince, M.I.T., Cambridge, MA
S. Plotkin	Lab. for Computer Scince, M.I.T., Cambridge, MA
G. Shannon	Computer Scinces Dept., Purdue University, West Lafayette, IN

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 46, Citation Count: 20

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/28395.28429 What is a DOI?

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 &Ogr;(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 (&Dgr; + 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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
	2	B. A werbuch. A tight lower bound on tile time of distributed maximal independent set algorithms. February 1987. Unpublished manuscript.
	3	B. Awerbuch , A. Israeli , Y. Shiloach, Finding euler circuits in logarithmic parallel time, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.249-257, December 1984 [doi>10.1145/800057.808688]
	4	Paul William Beame , S. A. Cook, Lower bounds in parallel machine computation, 1987
	5	P. Beame , J. Hastad, Optimal bounds for decision problems on the CRCW PRAM, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.83-93, January 1987, New York, New York, United States [doi>10.1145/28395.28405]
	6	A. Borodin , J. E. Hopcroft, Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences, v.30 n.1, p.130-145, Feb. 1985 [doi>10.1016/0022-0000(85)90008-X]
	7	J. Boyar and It. Karloff. Coloring planar graphs in parallel. 1986. Unpublished Manuscript.
	8	N. Chiba, T. Nishizeki, and N. Saito. A linear 5-color algorithm of planar graphs. Journal of Algorithms, 2:317-327, 1981.
	9	R Cole , U Vishkin, Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.206-219, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12151]
	10	Steven Fortune , James Wyllie, Parallelism in random access machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.114-118, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804339]
	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.
	12	R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
	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.
	14	Andrew V. Goldberg , Serge A. Plotkin, Parallel (&Dgr;+1)-coloring of constant-degree graphs, Information Processing Letters, v.25 n.4, p.241-245, June 17, 1987 [doi>10.1016/0020-0190(87)90169-4]
	15	A. V. Goldberg. Efficient Graph Algorithms for Sequential and Parallel Uomputers. PhD thesis, M.I.T., 1987.
	16	M. Goldberg and T. Spencer. A new parallel algorithm for the maximal independent set problem. 1986. Submitted for publication.
	17	F. Harary. Graph Theory. Addison-Wesley, 1972.
	18	Amos Israeli , Y. Shiloach, An improved parallel algorithm for maximal matching, Information Processing Letters, v.22 n.2, p.57-60, 1986 [doi>10.1016/0020-0190(86)90141-9]
	19	Richard M. Karp , Avi Wigderson, A fast parallel algorithm for the maximal independent set problem, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.266-272, December 1984 [doi>10.1145/800057.808690]
	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.
	21	C. Leiserson and B. Maggs. Communicationefficient parallel graph algorithms. In Proc. of International Conference o~ Parallel Processing, pages 861-868, 1986.
	22	C. Leiserson and C. Phillips. A fast parallel algorithm for region labeling. October 1986. (Extended abstract.).
	23	N. Linial. Locality as an obstacle to distributed computing. February 1987. Unpublished manuscript.
	24	Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
	25	M Luby, A simple parallel algorithm for the maximal independent set problem, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.1-10, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22146]
	26	David W. Matula , Yossi Shiloach , Robert E. Tarjan, Two linear-time algorithms for five-coloring a planar graph, Stanford University, Stanford, CA, 1980
	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.
	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.
	29	G. Shannon. Reduction techniques for designing linear-processor parallel algorithms on sparse graphs. 1986. (Extended Abstract).
	30	Justin R Smith, Parallel algorithms for depth-first searches I. planar graphs, SIAM Journal on Computing, v.15 n.3, p.814-830, August 1986 [doi>10.1137/0215058]

CITED BY 20

	Shay Kutten , David Peleg, Fast distributed construction of k-dominating sets and applications, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.238-251, August 20-23, 1995, Ottowa, Ontario, Canada
	Márió Szegedy , Sundar Vishwanathan, Locality based graph coloring, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.201-207, May 16-18, 1993, San Diego, California, United States
	Stephen Guattery , Gary L. Miller, A contraction procedure for planar directed graphs, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.431-441, June 29-July 01, 1992, San Diego, California, United States
	Yehuda Afek , Gad M. Landau , Baruch Schieber , Moti Yung, The power of multimedia: combining point-to point and multi-access networks, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.90-104, August 15-17, 1988, Toronto, Ontario, Canada
	Graham Cormode , S. Muthukrishnan, The string edit distance matching problem with moves, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.667-676, January 06-08, 2002, San Francisco, California
	Yehuda Afek , Michael Merritt , Gadi Taubenfeld , Dan Touitou, Disentangling multi-object operations (extended abstract), Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.111-120, August 21-24, 1997, Santa Barbara, California, United States
	Susanne Hambrusch , Xin He , Russ Miller, Parallel algorithms for gray-scale image component labeling on a mesh-connected computer, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.100-108, June 29-July 01, 1992, San Diego, California, United States
	F. Fich , V. Ramachandran, Lower bounds for parallel computation on linked structures, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.109-116, July 02-06, 1990, Island of Crete, Greece
	K. W. Ryu , J. JáJ', Efficient Algorithms for List Ranking and for Solving Graph Problems on the Hypercube, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.83-90, January 1990
	Lucia Draque Penso , Valmir C. Barbosa, A distributed algorithm to find k-dominating sets, Discrete Applied Mathematics, v.141 n.1-3, p.243-253, 30 May 2004
	Amotz Bar-Noy , Joseph Naor , Moni Naor, One bit algorithms, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.66-76, August 15-17, 1988, Toronto, Ontario, Canada
	Gianluca De Marco , Andrzej Pelc, Fast distributed graph coloring with O(&Dgr;) colors, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.630-635, January 07-09, 2001, Washington, D.C., United States
	Shay Kutten , David Peleg, Fault-local distributed mending (extended abstract), Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.20-27, August 20-23, 1995, Ottowa, Ontario, Canada
	Magnús Halldórsson , Jaikumar Radhakrishnan, Greed is good: approximating independent sets in sparse and bounded-degree graphs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.439-448, May 23-25, 1994, Montreal, Quebec, Canada
	Y. Han, An optimal linked list prefix algorithms on a local memory computer, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.278-286, February 21-23, 1989, Louisville, Kentucky
	Weizhao Wang , Xiang-Yang Li , Ophir Frieder , Yu Wang , Wen-Zhan Song, Efficient interference-aware TDMA link scheduling for static wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA
	Thomas Moscibroda , Roger Wattenhofer, Coloring unstructured radio networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Benoît Hudson , Gary L. Miller , Todd Phillips, Sparse parallel Delaunay mesh refinement, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Anders Dessmark , Andrzej Pelc, Distributed Colouring and Communication in Rings with Local Knowledge, Combinatorics, Probability and Computing, v.13 n.2, p.123-136, March 2004
	Shlomi Dolev , Nir Tzachar, Empire of colonies: Self-stabilizing and self-organizing distributed algorithm, Theoretical Computer Science, v.410 n.6-7, p.514-532, February, 2009