Abstract
Let G = (V,E) be a graph and V′ ⊆ V . We call V′ a (d,b)-ruling set if for all v i ,v j ∈ V′ the distance dist(v i ,v j ) ≥ d and V′ is b-dominating set (i.e. each vertex of G can be reached form some vertex from V′ by a path of length at most b).
Here we consider the problem of finding (d,b)-ruling set in a Unit Disc Graph. Unit Disc Graphs (UDG) are the most natural class of graphs to model wireless ad hoc networks (for example cell phones networks, wireless sensor networks etc.). The set of vertices of UDG is a set of points on the plane and two vertices, say v and w, are connected by an edge if and only if they are at the distance at most one in Euclidean norm (\(\left\|v,w\right\| \leq 1\)). We also assume that every vertex knows its position on the plane and, for such setting, present a deterministic algorithm which finds (d + 1,3d)-ruling set in UDG, and works in O(poly(d)) time (where d is a parameter).
As a result we are able improve time complexity (from O(log|V(G)|) to O(poly(d))) of several known algorithms for UDG, such as algorithm determining k-dominating set, maximum matching , minimum connected dominating set, minimum spanning tree and regular clustering.
This work was supported by grant N206 017 32/2452 for years 2007-2010.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.A.: Network decomposition and locality in distributed computation. In: IEEE Symposium on Foundations of Computer Science, pp. 364–369 (1989)
Linial, N., Saks, M.: Decomposing graphs into regions of small diameter. In: SODA 1991: Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, pp. 320–330. SIAM, Philadelphia (1991)
Panconesi, A., Srinivasan, A.: On the complexity of distributed network decomposition. J. Algorithms 20(2), 356–374 (1996)
Peleg, D.: Distributed computing: a locality-sensitive approach. In: Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2000)
Krzywdziński, K.: Distributed algorithm finding regular clustering in unit disc graphs, http://atos.wmid.amu.edu.pl/kkrzywd/research/REGULAR.pdf
Krzywdziński, K.: A local distributed algorithm to approximate mst in unit disc graphs. In: Gȩbala, M. (ed.) FCT 2009. LNCS, vol. 5699. Springer, Heidelberg (2009)
Czygrinow, A., Hańćkowiak, M.: Distributed approximation algorithms in unit-disk graphs. In: Dolev, S. (ed.) DISC 2006. LNCS, vol. 4167, pp. 385–398. Springer, Heidelberg (2006)
Fernandess, Y., Malkhi, D.: K-clustering in wireless ad hoc networks. In: POMC 2002 roceedings of the second ACM international workshop on Principles of mobile computing, pp. 31–37. ACM, New York (2002)
Czyzowicz, J., Dobrev, S., Fevens, T., González-Aguilar, H., Kranakis, E., Opatrny, J., Urrutia, J.: Local algorithms for dominating and connected dominating sets of unit disk graphs with location aware nodes. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol. 4957, pp. 158–169. Springer, Heidelberg (2008)
Kuhn, F., Moscibroda, T., Wattenhofer, R.: On the locality of bounded growth. In: PODC 2005Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, pp. 60–68. ACM Press, New York (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Krzywdziński, K. (2009). Efficient Construction of (d+1,3d)-Ruling Set in Wireless Ad Hoc Networks. In: Nguyen, N.T., Katarzyniak, R.P., Janiak, A. (eds) New Challenges in Computational Collective Intelligence. Studies in Computational Intelligence, vol 244. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03958-4_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-03958-4_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03957-7
Online ISBN: 978-3-642-03958-4
eBook Packages: EngineeringEngineering (R0)