Abstract
We give efficient deterministic distributed algorithms which given a graph G from a proper minor-closed family \(\mathcal{C}\) find an approximation of a minimum dominating set in G and a minimum connected dominating set in G. The algorithms are deterministic and run in a poly-logarithmic number of rounds. The approximation accomplished differs from an optimal by a multiplicative factor of (1+o(1)).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.A.: Network Decomposition and Locality in Distributed Computation. In: Proc. 30th IEEE Symp. on Foundations of Computer Science, pp. 364–369 (1989)
Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control 70, 32–53 (1986)
Czygrinow, A., Hańćkowiak, M.: Distributed algorithms for weighted problems in sparse graphs. Journal of Discrete Algorithms (2004) (in press)
Czygrinow, A., Hańćkowiak, M., Szymańska, E.: Distributed approximation algorithms for planar graphs. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds.) CIAC 2006. LNCS, vol. 3998. Springer, Heidelberg (2006)
Czygrinow, A., Hańćkowiak, M.: Distributed approximation algorithms in unit disk graphs (manuscript)
Diestel, R.: Graph Theory. Springer, New York (1997)
Dubhashi, D., Mei, A., Panconesi, A., Radhakrishnan, J., Srinivasan, A.: Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons. In: Proc. of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 717–724 (2003)
Elkin, M.: An Overview of Distributed Approximation. ACM SIGACT News Distributed Computing Column 35(4), 40–57 (2004) (whole number 132)
Kuhn, F., Wattenhofer, R.: Constant-Time Distributed Dominating Set Approximation. In: 22nd ACM Symposium on the Principles of Distributed Computing (PODC), Boston, Massachusetts, USA (July 2003)
Kuhn, F., Moscibroda, T., Wattenhofer, R.: What Cannot Be Computed Locally! In: Proceedings of 23rd ACM Symposium on the Principles of Distributed Computing (PODC), pp. 300–309 (2004)
Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Fast deterministic distributed maximal independent set computation on growth-bounded graphs. In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol. 3724, pp. 273–287. Springer, Heidelberg (2005)
Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Local Approximation Schemes for Ad Hoc and Sensor Networks. In: 3rd ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Cologne, Germany (2005)
Kutten, S., Peleg, D.: Fast distributed construction of k-dominating sets and applications. In: Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, pp. 238–251 (1995)
Linial, N.: Locality in distributed graph algorithms. SIAM Journal on Computing 21(1), 193–201 (1992)
Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036–1053 (1986)
Nesetril, J., Ossona de Mendez, P.: Colorings and homomorphisms of minor closed classes. In: Aronov, B., Basu, S., Pach, J., Sharir, M. (eds.) Discrete and Computational Geometry, The Goodman-Pollack Festschrift, Algorithms and Combinatorics, vol. 25, pp. 651–664. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Czygrinow, A., Hańćkowiak, M. (2006). Distributed Almost Exact Approximations for Minor-Closed Families. In: Azar, Y., Erlebach, T. (eds) Algorithms – ESA 2006. ESA 2006. Lecture Notes in Computer Science, vol 4168. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11841036_24
Download citation
DOI: https://doi.org/10.1007/11841036_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-38875-3
Online ISBN: 978-3-540-38876-0
eBook Packages: Computer ScienceComputer Science (R0)