Locality based graph coloring

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Locality based graph coloring

Full text

Pdf (716 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 201 - 207

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Márió Szegedy
Sundar Vishwanathan

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 55, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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/167088.167156 What is a DOI?

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	Noga Alon , Amotz Bar-Noy , Nathan Linial , David Peleg, A lower bound for radio broadcast, Journal of Computer and System Sciences, v.43 n.2, p.290-298, Oct. 1991 [doi>10.1016/0022-0000(91)90015-W]
	2	Noga Alon , Amotz Bar-Noy , Nathan Linial , David Peleg, Single round simulation on radio networks, Journal of Algorithms, v.13 n.2, p.188-210, June, 1992 [doi>10.1016/0196-6774(92)90015-5]
	3	A.E. Brouwer, J.B. Shearer, N.J. Sloane, W. D. Smith, A new table of constant weight codes, IEEE Transactions on information Theory vol. 36 (nov 1990), 1334-1380.
	4	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]
	5	P. ErdSs, P. Frankl, and Z. Ffiredi. Pamilies of finite sets in which no set is covered by the union of r others. Israel J. Math., 51:79-89, 1985.
	6	A. Goldberg , S. Plotkin , G. Shannon, Parallel symmetry-breaking in sparse graphs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.315-324, January 1987, New York, New York, United States [doi>10.1145/28395.28429]
	7	D. J. Kleitman, J. Shearer, and D. Sturtevant. Intersections of k-element sets. Combinatorica, 1:381-384, 1981.
	8	N. Linial. Distributive graph algorithms-global solutions from local data. In FOCS, pages 331-335, 1987.
	9	Nathan Linial, Locality in distributed graph algorithms, SIAM Journal on Computing, v.21 n.1, p.193-201, Feb. 1992 [doi>10.1137/0221015]
	10	Sundar Vishwanathan. Locality Based Graph Coloring. Preprint

CITED BY 3

	Stefano Basagni , Danilo Bruschi, A logarithmic lower bound for time-spread multiple-access (TSMA) protocols, Wireless Networks, v.6 n.2, p.161-163, 1999
	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
	Sándor Gyri, Coding for a multiple access OR channel: A survey, Discrete Applied Mathematics, v.156 n.9, p.1407-1430, May, 2008