Constant-time distributed dominating set approximation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Constant-time distributed dominating set approximation

Full text

Pdf (765 KB)

Source

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

Boston, Massachusetts

Pages: 25 - 32

Year of Publication: 2003

ISBN:1-58113-708-7

Authors

Fabian Kuhn	ETH Zurich, Zurich, Switzerland
Roger Wattenhofer	ETH Zurich, Zurich, Switzerland

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): 8, Downloads (12 Months): 33, Citation Count: 33

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/872035.872040 What is a DOI?

ABSTRACT

Finding a small dominating set is one of the most fundamental problems of traditional graph theory. In this paper, we present a new fully distributed approximation algorithm based on LP relaxation techniques. For an arbitrary parameter k and maximum degree Δ, our algorithm computes a dominating set of expected size O(kΔ^2/k log Δ|DS_OPT|) in O(k²) rounds where each node has to send O(k²Δ) messages of size O(logΔ). This is the first algorithm which achieves a non-trivial approximation ratio in a constant number of rounds.

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	Khaled M. Alzoubi , Peng-Jun Wan , Ophir Frieder, Message-optimal connected dominating sets in mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513820]
	2	Yair Bartal , John W. Byers , Danny Raz, Global Optimization Using Local Information with Applications to Flow Control, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.303, October 19-22, 1997
	3	Bonnie Berger , John Rompel , Peter W. Shor, Efficient NC algorithms for set cover with applications to learning and geometry, Journal of Computer and System Sciences, v.49 n.3, p.454-477, Dec. 1994
	4	V. Chvátal. Linear Programming. W. H. Freeman and Company, 1983.
	5	Devdatt Dubhashi , Alessandro Mei , Alessandro Panconesi , Jaikumar Radhakrishnan , Arvind Srinivasan, Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	6	Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
	7	Jie Gao , Leonidas Guibas , John Hershberger , Li Zhang , An Zhu, Discrete mobile centers, Proceedings of the seventeenth annual symposium on Computational geometry, p.188-196, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378666]
	8	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
	9	Sudipto Guha , Samir Khuller, Approximation Algorithms for Connected Dominating Sets, Proceedings of the Fourth Annual European Symposium on Algorithms, p.179-193, September 25-27, 1996
	10	L. Jia, R. Rajaraman, and R. Suel. An Efficient Distributed Algorithm for Constructing Small Dominating Sets. In Proc. of the 20th ACM Symposium on Principles of Distributed Computing (PODC), pages 33--42, 2001.
	11	D. S. Johnson. Approximation Algorithms for Combinatorial Problems. Journal of Computer and System Sciences, 9:256--278, 1974.
	12	R. M. Karp. Reducibility Among Combinatorial Problems. In Proc. of a Symposium on the Complexity of Computer Computations, pages 85--103, 1972.
	13	Shay Kutten , David Peleg, Fast distributed construction of small k-dominating sets and applications, Journal of Algorithms, v.28 n.1, p.40-66, July 1, 1998 [doi>10.1006/jagm.1998.0929]
	14	L. Lovasz. On the Ratio of Optimal Integral and Fractional Covers. Discrete Mathematics, 13:383--390, 1975.
	15	Michael Luby , Noam Nisan, A parallel approximation algorithm for positive linear programming, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.448-457, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167211]
	16	Sridhar Rajagopalan , Vijay V. Vazirani, Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs, SIAM Journal on Computing, v.28 n.2, p.525-540, April 1999 [doi>10.1137/S0097539793260763]
	17	Rajmohan Rajaraman, Topology control and routing in ad hoc networks: a survey, ACM SIGACT News, v.33 n.2, June 2002 [doi>10.1145/564585.564602]
	18	Petr Slavík, A tight analysis of the greedy algorithm for set cover, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.435-441, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237991]
	19	Jie Wu , Hailan Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.7-14, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313261]

CITED BY 33

	Martin Burkhart , Pascal von Rickenbach , Roger Wattenhofer , Aaron Zollinger, Does topology control reduce interference?, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan
	Michael Elkin, Distributed approximation: a survey, ACM SIGACT News, v.35 n.4, December 2004
	Yu Wang , WeiZhao Wang , Xiang-Yang Li, Distributed low-cost backbone formation for wireless ad hoc networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA
	Fabian Kuhn , Aaron Zollinger, Ad-hoc networks beyond unit disk graphs, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.69-78, September 19, 2003, San Diego, CA, USA
	Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, The price of being near-sighted, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.980-989, January 22-26, 2006, Miami, Florida
	Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, Initializing newly deployed ad hoc and sensor networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA
	P. Brighten Godfrey , David Ratajczak, Naps: scalable, robust topology management in wireless ad hoc networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA
	Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, Brief announcement: efficient clustering in unstructured radio networks, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Michael Elkin, Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Ossama Younis , Sonia Fahmy, HEED: A Hybrid, Energy-Efficient, Distributed Clustering Approach for Ad Hoc Sensor Networks, IEEE Transactions on Mobile Computing, v.3 n.4, p.366-379, October 2004
	Thomas Moscibroda , Roger Wattenhofer, Facility location: distributed approximation, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, On the locality of bounded growth, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Kishore Kothapalli , Christian Scheideler , Melih Onus , Andrea Richa, Constant density spanners for wireless ad-hoc networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Guanghui He , Rong Zheng , Indranil Gupta , Lui Sha, A framework for time indexing in sensor networks, ACM Transactions on Sensor Networks (TOSN), v.1 n.1, p.101-133, August 2005
	Fabian Kuhn , Tim Nieberg , Thomas Moscibroda , Roger Wattenhofer, Local approximation schemes for ad hoc and sensor networks, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany
	Budhaditya Deb , Badri Nath, On the node-scheduling approach to topology control in ad hoc networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA
	F. Grandoni , J. Könemann , A. Panconesi , M. Sozio, Primal-dual based distributed algorithms for vertex cover with semi-hard capacities, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, What cannot be computed locally!, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Chengdu Huang , Tarek Abdelzaher, Bounded-Latency Content Distribution: Feasibility and Evaluation, IEEE Transactions on Computers, v.54 n.11, p.1422-1437, November 2005
	Qixiang Sun , Neil Daswani , Hector Garcia-Molina, Maximizing remote work in flooding-based peer-to-peer systems, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.10, p.1583-1598, 14 July 2006
	A. Czygrinow , M. Hańćkowiak, Distributed algorithms for weighted problems in sparse graphs, Journal of Discrete Algorithms, v.4 n.4, p.588-607, December, 2006
	Rajiv Gandhi , Srinivasan Parthasarathy, Distributed algorithms for connected domination in wireless networks, Journal of Parallel and Distributed Computing, v.67 n.7, p.848-862, July, 2007
	Fabian Kuhn , Roger Wattenhofer , Aaron Zollinger, Ad hoc networks beyond unit disk graphs, Wireless Networks, v.14 n.5, p.715-729, October 2008
	Bo Han, Zone-based virtual backbone formation in wireless ad hoc networks, Ad Hoc Networks, v.7 n.1, p.183-200, January, 2009
	Christian Scheideler , Andrea Richa , Paolo Santi, An O(log n) dominating set protocol for wireless ad-hoc networks under the physical interference model, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, May 26-30, 2008, Hong Kong, Hong Kong, China
	Christoph Lenzen , Yvonne Anne Oswald , Roger Wattenhofer, What can be approximated locally?: case study: dominating sets in planar graphs, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Yanjing Sun , Xiangping Gu , Jiansheng Qian, Construction of virtual backbone on growth-bounded graph with variable transmission range, WSEAS Transactions on Computers, v.7 n.1, p.32-38, January 2008
	Baruch Awerbuch , Rohit Khandekar, Stateless distributed gradient descent for positive linear programs, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Oliver Wellnitz , Lars Wolf, Assigning game server roles in mobile ad-hoc networks, Proceedings of the 2006 international workshop on Network and operating systems support for digital audio and video, November 22-23, 2006, Newport, Rhode Island
	Alessandro Panconesi , Mauro Sozio, Fast distributed scheduling via primal-dual, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Pascal von Rickenbach , Roger Wattenhofer , Aaron Zollinger, Algorithmic models of interference in wireless ad hoc and sensor networks, IEEE/ACM Transactions on Networking (TON), v.17 n.1, p.172-185, February 2009
	Christos Koufogiannakis , Neal E. Young, Distributed and parallel algorithms for weighted vertex cover and other covering problems, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	Saurav Pandit , Sriram Pemmaraju, Return of the primal-dual: distributed metric facilitylocation, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada