Fast network decomposition

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast network decomposition

Full text

Pdf (748 KB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the eleventh annual ACM symposium on Principles of distributed computing table of contents

Vancouver, British Columbia, Canada

Pages: 169 - 177

Year of Publication: 1992

ISBN:0-89791-495-3

Authors

Baruch Awerbuch	Dept. of Mathematics and Lab. for Computer Science, M.I.T., Cambridge, MA
Bonnie Berger	Dept. of Mathematics and Lab. for Computer Science, M.I.T., Cambridge, MA
Lenore Cowen	Dept. of Mathematics and Lab. for Computer Science, M.I.T., Cambridge, MA
David Peleg	Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot, 76100, Israel

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 17, Citation Count: 5

Additional Information:

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/135419.135456 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	Y. Afek, B. Awerbuch, and E. Gafni. Applying static network protocols to dynamic networks. In Proc. 28th IEEE Syrup. on Foundations of Computer Science, pages 358-370, Oct. 1987.
	2	Y. Afek and M. Rickhn. Sparser: A paradigm for running distributed algorithms. Unpublished manuscript, 1991.
	3	Yehuda Afek , Moty Ricklin, Sparser: a paradigm for running distributed algorithms, Journal of Algorithms, v.14 n.2, p.316-328, March 1993 [doi>10.1006/jagm.1993.1016]
	4	B. Awerbuch, A. Baratz, and D. Peleg. Efficient broadcast and light-weight spanners. Unpublished manuscript, Nov. 1991.
	5	B. Awerbuch, B. Berger, L. Cowen, and D. Peleg. Fast deterministic cover algorthms. Unpublished manuscript, Nov. 1991.
	6	Baruch Awerbuch , Bonnie Berger , Lenore Cowen , David Peleg, Low-Diameter Graph Decomposition is in NC, Proceedings of the Third Scandinavian Workshop on Algorithm Theory, p.83-93, July 08-10, 1992
	7	Baruch Awerbuch , Israel Cidon , Inder Gopal , Marc Kaplan , Shay Kutten, Distributed control for PARIS, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.145-159, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93412]
	8	B. Awerbuch, A. Goldberg, M. Luby, and S. Plotkin. Network decomposition and locality in distributed computation. In Proc. 30th IEEE Syrup. on Foundations of Computer Science, May 1989.
	9	B. Awerbuch, S. Kutten, and D. Peleg. On buffer-economical store-and-forward deadlock prevention. In Proc. of the 1991 INFOCOM, 1991.
	10	Baruch Awerbuch , Shay Kutten , David Peleg, Competitive distributed job scheduling (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.571-580, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129768]
	11	Baruch Awerbuch , Boaz Patt-Shamir , David Peleg , Michael Saks, Adapting to asynchronous dynamic networks (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.557-570, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129767]
	12	B. Awerbuch and D. Peleg. Network synchronization with polylogarithmic overhead. In Proc. 31st IEEE Syrup. on Foundations of Computer Science, pages 514-522~ 1990.
	13	B. Awerbuch and D. Peleg. Sparse partitions. In Proc. 31st IEEE $ymp. on Foundations of Computer Science, pages 503-513, 1990.
	14	Baruch Awerbuch , David Peleg, Routing with polynomial communication-space trade-off, SIAM Journal on Discrete Mathematics, v.5 n.2, p.151-162, May 1992 [doi>10.1137/0405013]
	15	Yair Bartal , Amos Fiat , Yuval Rabani, Competitive algorithms for distributed data management (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.39-50, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129717]
	16	Nathan Linial , Michael Saks, Decomposing graphs into regions of small diameter, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.320-330, January 28-30, 1991, San Francisco, California, United States
	17	Alessandro Panconesi , Aravind Srinivasan, Improved distributed algorithms for coloring and network decomposition problems, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.581-592, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129769]
	18	D. Peleg. Distance-preserving distributed directories and efficient routing schemes, unpublished manuscript, 1989.
	19	Satish B. Rao, Faster algorithms for finding small edge cuts in planar graphs, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.229-240, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129735]

CITED BY 5

	Michał Hańćkowiak , Michał Karoński , Alessandro Panconesi, A faster distributed algorithm for computing maximal matchings deterministically, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.219-228, May 04-06, 1999, Atlanta, Georgia, United States
	Michał Hańćkowiak , Michał Karoński , Alessandro Panconesi, On the distributed complexity of computing maximal matchings, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.219-225, January 25-27, 1998, San Francisco, California, United States
	Baruch Awerbuch , David Peleg, Online tracking of mobile users, Journal of the ACM (JACM), v.42 n.5, p.1021-1058, Sept. 1995
	Roche A. Guérin , Ariel Orda, QoS routing in networks with inaccurate information: theory and algorithms, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.350-364, June 1999
	Michael Elkin , Guy Kortsarz, Improved schedule for radio broadcast, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia