Multicasting in heterogeneous networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Multicasting in heterogeneous networks

Full text

Pdf (844 KB)

Source

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

Dallas, Texas, United States

Pages: 448 - 453

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Amotz Bar-Noy	Electrical Engineering Department, Tel Aviv University, Tel Aviv 69978, Israel
Sudipto Guha	Computer Science Department, Stanford University, Stanford, CA
Joseph (Seffi) Naor	Computer Science Department, Technion, Haifa 32000, Israel
Baruch Schieber	IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 25, Citation Count: 11

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/276698.276857 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	Vasanth Bala , Jehoshua Bruck , Raymond Bryant , Robert Cypher , Peter de Jong , Pablo Elustondo , D. Frye , Alex Ho , Ching-Tien Ho , Gail Irwin , Shlomo Kipnis , Richard Lawrence , Marc Snir, The IBM external user interface for scalable parallel systems, Parallel Computing, v.20 n.4, p.445-462, April 1994 [doi>10.1016/0167-8191(94)90022-1]
	2	Vasanth Bala , Shlomo Kipnis , Marc Snir , Jehoshua Bruck , Robert Cypher , Pablo Elustondo , Alex Ho , Ching-Tien Ho, CCL: A Portable and Tunable Collective Communication Library for Scalable Parallel Computers, Proceedings of the 8th International Symposium on Parallel Processing, p.835-844, April 01, 1994
	3	A. Bar-Noy , S. Kipnis, Designing broadcasting algorithms in the Postal Model for message-passing systems, Mathematical Systems Theory, v.27 n.5, p.431-452, Sept./Oct. 1994
	4	Michael J. Dinneen , Michael R. Fellows , Vance Faber, Algebraic Constructions of Efficient Broadcast Networks, Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.152-158, October 07-11, 1991
	5	$, DONOARRA El' AL., Document for a standard message. passht# interface, Message Passing Interface Forum, November 1993.
	6	Express 3,0 hltroduetory Guide, Parasoft Corporation, 1990.
	7	Uriel Feige, A threshold of ln n for approximating set cover (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.314-318, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237977]
	8	Geoffrey C. Fox , Mark A. Johnson , Gregory A. Lyzenga , Steve W. Otto , John K. Salmon , David W. Walker, Solving problems on concurrent processors. Vol. 1: General techniques and regular problems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
	9	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	10	L. GARaANO AND U. V^CCAgO, On the constructt3n ofm~n. imal broadcast networks, Networks, %1. 19, pp. 373-389, 1989.
	11	Michelangelo Grigni , David Peleg, Tight bounds on minimum broadcast networks, SIAM Journal on Discrete Mathematics, v.4 n.2, p.207-222, May 1991 [doi>10.1137/0404021]
	12	$. M. H~~II, $. T. HED~tI, AND A. L. LmSTMAN, A survey of gossiping and broadcasting in communication networks, Networks, Vol. 18, No. 4, pp. 319-349,1988.
	13	R.M. KARP, F. T. LEIGHTON, R. L. R.W~T, C. D. THOMPSON, U. V. VAZIRANI, AND V. V. V~I, Global wire routing in two-dimensional arrays, Algorithmica, Vol. 2, pp. 113-129, 1987.
	14	Guy Kortsarz , David Peleg, Approximation Algorithms for Minimum-Time Broadcast, SIAM Journal on Discrete Mathematics, v.8 n.3, p.401-427, Aug. 1995 [doi>10.1137/S0895480193245923]
	15	Richard M. Karp , Abhijit Sahay , Eunice E. Santos , Klaus Erik Schauser, Optimal broadcast and summation in the LogP model, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.142-153, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165250]
	16	Arthur L. Liestman , Joseph G. Peters, Broadcast networks of bounded degree, SIAM Journal on Discrete Mathematics, v.1 n.4, p.531-540, Nov. 1988 [doi>10.1137/0401049]
	17	Martin Middendorf, Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2, Information Processing Letters, v.46 n.6, p.281-287, July 26, 1993 [doi>10.1016/0020-0190(93)90066-I]
	18	R. RAVi, Rapid rumor ramification: approMmating the minimum broadcasting time, 35th Syrup. on Foundations of Computer Science, IE , pp. 202-213,1994.
	19	D. RICHARDS AND A. L. Lm~tAlq, Generalizations of broadcasting and gossiping, Networks, %1. 18, pp. 125-.138, 1988.
	20	Aravind Srinivasan , Chung-Piaw Teo, A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.636-643, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258658]
	21	J.A. V~mlRA AIqD X. WElqO, A new method for constructing minimal broadcast networks, Networks, Vol. 23, pp. 481..497, 1993.
	22	D. B. WEST, A class of solutions to the gossip problem, Part i, Discrete Math., Vol. 39, pp. 307-326,1992.

CITED BY 11

	Micah Adler , Tom Leighton, Compression using efficient multicasting, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.153-162, May 21-23, 2000, Portland, Oregon, United States
	Michael Elkin , Guy Kortsarz, Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Pangfeng Liu , Tzu-Hao Sheng, Broadcast scheduling optimization for heterogeneous cluster systems, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.129-136, July 09-13, 2000, Bar Harbor, Maine, United States
	Samir Khuller , Yoo-Ah Kim , Yung-Chun Justin Wan, Broadcasting on networks of workstations, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Esther M. Arkin , Michael A. Bender , Sándor P. Fekete , Joseph S. B. Mitchell , Martin Skutella, The freeze-tag problem: how to wake up a swarm of robots, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.568-577, January 06-08, 2002, San Francisco, California
	Pangfeng Liu, Broadcast scheduling optimization for heterogeneous cluster systems, Journal of Algorithms, v.42 n.1, p.135-152, January 2002
	Samir Khuller , Yoo-Ah Kim, On broadcasting in heterogenous networks, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Pierre Fraigniaud, A note on line broadcast in digraphs under the edge-disjoint paths mode, Discrete Applied Mathematics, v.144 n.3, p.320-323, 15 December 2004
	Esther M. Arkin , Michael A. Bender , Dongdong Ge, Improved approximation algorithms for the freeze-tag problem, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Michael Elkin , Guy Kortsarz, Sublogarithmic approximation for telephone multicast: path out of jungle (extended abstract), Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Hovhannes Harutyunyan , George Laza , Edward Maraachlian, Broadcasting in necklace graphs, Proceedings of the 2nd Canadian Conference on Computer Science and Software Engineering, May 19-21, 2009, Montreal, Quebec, Canada