research-article

A local algorithm for dominating sets of quasi-unit disk graphs

Authors:

Jaroslav OpatrnyAuthors Info & Claims

C3S2E '09: Proceedings of the 2nd Canadian Conference on Computer Science and Software Engineering

Pages 223 - 231

https://doi.org/10.1145/1557626.1557663

Published: 19 May 2009 Publication History

Abstract

A quasi-unit disk graph has been used as a realistic model of an ad-hoc or a sensor wireless network. A wireless ad-hoc network is location aware if each node knows its geographic coordinates. Some network backbones proposed for data gathering in a wireless network are based on dominating sets of the network graph. The location awareness of ad-hoc networks corresponding to unit disk graph was used in [6] to obtain a local algorithm for a dominating set of a unit disk graph. In this paper we generalize this algorithm to location aware ad-hoc networks corresponding to quasi-unit graphs. The competitive ratio of the algorithm is determined for several ranges of the parameter r of an r--quasi-unit disk graph. For each range of r the competitive ratio is shown to be a constant value. An experimental evaluation of the algorithm is also carried out, which confirms very good performance of our algorithm.

References

[1]

M. Barbeau, I. Nikolaidis, and E. Kranakis(eds). Ad-Hoc, Mobile, and Wireless Networks. LNCS 2865, 2004.

Digital Library

[2]

L. Barrière, P. Fraigniaud, L. Narayanan, and J. Opatrny. Robust position-based routing in wireless ad-hoc networks with unstable transmission ranges. Wireless Communications and Mobile Computing Journal, 3/2:141--153, 2003. Extended abstract in Proceedings of Dial M for Mobility, 2000.

[3]

K. Cai. Design and analysis of a connected dominating set algorithm for mobile ad hoc networks. Master's thesis, University of British Colombnia, 2004.

[4]

V. Chvátal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3):233--235, 1979.

Digital Library

[5]

B. N. Clark, C. J. Colbourn, and D. S. Johnson. Unit disk graphs. Discrete Mathematics, 86:165--177, 1990.

Digital Library

[6]

J. Czyzowicz, S. Dobrev, T. Fevens, H. Gonzalez-Aguilar, E. Kranakis, J. Opatrny, and J. Urutia. Local algorithms for dominating and connected dominating sets of unit disk graphs. In Proceedings of Latin08, LNCS 4957, pages 158--169, 2008.

Digital Library

[7]

F. Dai and J. Wu. An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE Trans. on Parallel and Distributed Systems, 15:13, oct 2004.

Digital Library

[8]

B. Gao, Y. Yang, and H. Ma. On calculating minimum connected dominating set for wireless ad hoc networks using A new distributed heuristic algorithm. In H. R. Arabnia, L. T. Yang, and C.-H. Yeh, editors, ICWN, pages 946--951. CSREA Press, 2004.

[9]

M. Garey and D. Johnson. Computers and Intractability - A Guide to the Theory of NP-completeness. Freeman, 1979.

Digital Library

[10]

M. Hassinen, V. Polishchuk, and J. Suomela. Local 3-approximation algorithms for weighted dominating set and vertex cover in quasi unit-disk graphs. In proceedings of DCOSS'08, pages 9--12. ACM Press, 2008.

[11]

M. Hauspie, A. Panier, and D. Simplot-Ryl. Localized probabilistic and dominating set based algorithm for efficient information dissemination in ad hoc networks. In Proceedings of IEE conference on Mobile Ad-hoc and Sensor Systems, pages 11--20, 2004.

[12]

T. Haynes, S. Hedentiemi, and P. Slater. Fundamentals of domination in graphs. Dekker, 1998.

[13]

L. Jia, R. Rajaraman, and R. Suel. An efficient distributed algorithm for constructing small dominating sets. Distributed Computing, 15, 2002.

Digital Library

[14]

F. Kuhn and R. Wattenhofer. Constant-time distributed dominating set approximation. Distributed Computing, 17(4):303--310, 2005.

Digital Library

[15]

F. Kuhn, R. Wattenhofer, and A. Zollinger. Ad-hoc networks beyond unit disk graphs. In 1st ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), San Diego, California, USA, 2003.

Digital Library

[16]

N. Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193--201, Feb. 1992.

Digital Library

[17]

Maple. Maple User Manual. Maplesoft, 2007.

[18]

A. Wiese and E. Kranakis. Local ptas for independent set and vertex cover in location aware unit disk graphs. In proceedings of DCOSS 2008, LNCS 5067, pages 415--431. Springer-Verlag, 2008.

Digital Library

[19]

J. Wu and H. Li. On calculating connected dominating set for efficient routing in ad hoc wireless networks. In DIAL-M, pages 7--14. ACM, 1999.

Digital Library

Cited By

Sharma BBhatia RSingh A(2016)A hierarchical virtual backbone construction protocol for mobile ad hoc networksJournal of King Saud University - Computer and Information Sciences10.1016/j.jksuci.2014.06.02028:3(276-288)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.jksuci.2014.06.020

Index Terms

A local algorithm for dominating sets of quasi-unit disk graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows

Recommendations

Local algorithms for dominating and connected dominating sets of unit disk graphs with location aware nodes
LATIN'08: Proceedings of the 8th Latin American conference on Theoretical informatics

Many protocols in ad-hoc networks use dominating and connected dominating sets, for example for broadcasting and routing. For large ad hoc networks the construction of such sets should be local in the sense that each node of the network should make ...
On dominating sets of maximal outerplanar and planar graphs

A set D V ( G ) of a graph G is a dominating set if every vertex v V ( G ) is either in D or adjacent to a vertex in D . The domination number γ ( G ) of a graph G is the minimum cardinality of a dominating set of G . Campos and Wakabayashi (2013) and ...
Local construction of connected dominating sets in wireless ad hoc networks

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

C3S2E '09: Proceedings of the 2nd Canadian Conference on Computer Science and Software Engineering

May 2009

266 pages

ISBN:9781605584010

DOI:10.1145/1557626

Editors:
Bipin C. Desai
Concordia University
,
Carson K. Leung
University of Manitoba

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

BytePress
Concordia University: Concordia University

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 May 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

C3S2E '09

Sponsor:

Concordia University

C3S2E '09: Proceedings of the 2009 C3S2E conference

May 19 - 21, 2009

Quebec, Montreal, Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
168
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sharma BBhatia RSingh A(2016)A hierarchical virtual backbone construction protocol for mobile ad hoc networksJournal of King Saud University - Computer and Information Sciences10.1016/j.jksuci.2014.06.02028:3(276-288)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.jksuci.2014.06.020

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten