Abstract
Given a set of points Q in the plane, define the \(\frac{r}{2}\)-Disk Graph, Q(r), as a generalized version of the Unit Disk Graph: the vertices of the graph is Q and there is an edge between two points in Q iff the distance between them is at most r. In this paper, motivated by applications in wireless sensor networks, we study the following geometric problem of color-spanning sets: given n points with m colors in the plane, choosing m points P with distinct colors such that the \(\frac{r}{2}\)-Disk Graph, P(r), is connected and r is minimized. When at most two points are of the same color c i (or, equivalently, when a color c i spans at most two points), we prove that the problem is NP-hard to approximate within a factor 3 − ε. And we present a tight factor-3 approximation for this problem. For the more general case when each color spans at most k points, we present a factor-(2k-1) approximation. Our solutions are based on the applications of the famous Hall’s Marriage Theorem on bipartite graphs, which could be useful for other problems.
This research is partially funded by the International Science and Technology Cooperation Program of China (2010DFA92720-08-1) and NSF of China under project 11271351.
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
Abellanas, M., Hurtado, F., Icking, C., Klein, R., Langetepe, E., Ma, L., Palop, B., Sacristan, V.: The farthest color Voronoi diagram and related problems. In: Proceedings of the 17th European Workshop on Computational Geometry (EWCG 2001), pp. 113–116 (2001)
Abellanas, M., Hurtado, F., Icking, C., Klein, R., Langetepe, E., Ma, L., Palop, B., Sacristan, V.: Smallest Color-Spanning Objects. In: Proc. 9th Annu. European Sympos. Algorithms, pp. 278–289 (2001)
Beresford, A.R., Stajano, F.: Location privacy in pervasive computing. IEEE Pervasive Computing 2(1), 46–55 (2003)
Cheema, M.A., Lin, X., Wang, W., Zhang, W., Pei, J.: Probabilistic Reverse Nearest Neighbor Queries on Uncertain Data. IEEE Trans. Knowl. Data Eng. 22(4), 550–564 (2010)
Cheng, R., Kalashnikov, D.V., Prabhakar, S.: Querying imprecise data in moving object environments, knowledge and data engineering. IEEE Transactions on Knowledge and Data Engineering 16(9), 1112–1127 (2004)
Cheng, R., Zhang, Y., Bertino, E., Prabhakar, S.: Preserving user location privacy in mobile data management infrastrutures. In: Danezis, G., Golle, P. (eds.) PET 2006. LNCS, vol. 4258, pp. 393–412. Springer, Heidelberg (2006)
Cole, R., Ost, K., Schirra, S.: On edge coloring bipartite graphs. Combinatorica 21(1), 5–12 (2001)
Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press (2001)
Das, S., Goswani, P.P., Nandy, S.C.: Smallest color-spanning object revised. International Journal of Computational Geometry and Applications 19(5), 457–478 (2009)
Efrat, A., Fekete, S.P., Gaddehosur, P.R., Mitchell, J.S.B., Polishchuk, V., Suomela, J.: Improved approximation algorithms for relay placement. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 356–367. Springer, Heidelberg (2008)
Fleischer, R., Xu, X.: Computing Minimum Diameter Color-Spanning Sets. In: Lee, D.-T., Chen, D.Z., Ying, S. (eds.) FAW 2010. LNCS, vol. 6213, pp. 285–292. Springer, Heidelberg (2010)
Gedik, B., Liu, L.: A customizable k-anonymity model for protecting location privacy. In: Proceedings of the 25th International Conference on Distributed Computing Systems (ICDCS 2005), pp. 620–629 (2005)
Goel, A., Kapralov, M., Khanna, S.: Perfect matchings in O(nlogn) time in regular bipartite graphs. In: Proceedings of STOC 2010, pp. 39–46 (2010)
Hall, P.: On representatives of subsets. J. London Math. Soc. 10(1), 26–30 (1935)
Hopcroft, J., Karp, R.: An n 5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225–231 (1973)
Ju, W., Fan, C., Luo, J., Zhu, B., Daescu, O.: On Some Geometric Problems of Color-Spanning Sets. J. of Combinatorial Optimization 26(2), 266–283 (2013)
Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982)
Mumey, B., Spendlove, K., Zhu, B.: Extending the lifetime of a WSN by partial covers. In: Proceedings of IEEE ICC 2013 (2013)
Pei, J., Jiang, B., Lin, X., Yuan, Y.: Probabilistic Skylines on Uncertain Data. In: Proc. of VLDB 2007, pp. 15–26 (2007)
Pfoser, D., Jensen, C.S.: Capturing the uncertainty of moving-objects representations. In: Güting, R.H., Papadias, D., Lochovsky, F.H. (eds.) SSD 1999. LNCS, vol. 1651, pp. 111–131. Springer, Heidelberg (1999)
Sistla, P.A., Wolfson, O., Chamberlain, S., Dao, S.: Querying the uncertain position of moving objects. In: Etzion, O., Jajodia, S., Sripada, S. (eds.) Temporal Databases-Research and Practice. LNCS, vol. 1399, pp. 310–337. Springer, Heidelberg (1998)
Tarjan, R.: Efficiency of a good but not linear set union algorithm. J. of ACM 22(2), 215–225 (1975)
Yang, Y., Lin, M., Xu, J., Xie, Y.: Minimum spanning tree with neighborhoods. In: Kao, M.-Y., Li, X.-Y. (eds.) AAIM 2007. LNCS, vol. 4508, pp. 306–316. Springer, Heidelberg (2007)
Yuen, S.-M., Tao, Y., Xiao, X., Pei, J., Zhang, D.: Superseding Nearest Neighbor Search on Uncertain Spatial Databases. IEEE Trans. Knowl. Data Eng. 22(7), 1041–1055 (2010)
Zhang, D., Chee, Y.M., Mondal, A., Tung, A.K.H., Kitsuregawa, M.: Keyword search in spatial databases: Towards searching by document. In: Proceedings of the 25th IEEE International Conference on Data Engineering (ICDE 2009), pp. 688–699 (2009)
Zhang, H., Hou, J.C.: Maintaining sensing coverage and connectivity in large sensor networks. Ad Hoc & Sensor Wireless Networks, an Intl J. 1, 89–124 (2005)
Zhang, H., Nixon, P., Dobson, S.: Partial coverage in homological sensor networks. In: Proceedings of the 5th IEEE Intl. Conf. on Wireless and Mobile Computing, Networking and Communications (WiMob 2009), pp. 42–47 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fan, C., Luo, J., Zhu, B. (2013). Tight Approximation Bounds for Connectivity with a Color-Spanning Set. In: Cai, L., Cheng, SW., Lam, TW. (eds) Algorithms and Computation. ISAAC 2013. Lecture Notes in Computer Science, vol 8283. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45030-3_55
Download citation
DOI: https://doi.org/10.1007/978-3-642-45030-3_55
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45029-7
Online ISBN: 978-3-642-45030-3
eBook Packages: Computer ScienceComputer Science (R0)