{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:26:27Z","timestamp":1760441187323},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642450297"},{"type":"electronic","value":"9783642450303"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-45030-3_55","type":"book-chapter","created":{"date-parts":[[2013,12,11]],"date-time":"2013-12-11T21:32:52Z","timestamp":1386797572000},"page":"590-600","source":"Crossref","is-referenced-by-count":3,"title":["Tight Approximation Bounds for Connectivity with a Color-Spanning Set"],"prefix":"10.1007","author":[{"given":"Chenglin","family":"Fan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Luo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Binhai","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"55_CR1","unstructured":"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\u2013116 (2001)"},{"key":"55_CR2","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1007\/3-540-44676-1_23","volume-title":"Algorithms \u2014 ESA 2001","author":"Manuel Abellanas","year":"2001","unstructured":"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\u2013289 (2001)"},{"issue":"1","key":"55_CR3","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1109\/MPRV.2003.1186725","volume":"2","author":"A.R. Beresford","year":"2003","unstructured":"Beresford, A.R., Stajano, F.: Location privacy in pervasive computing. IEEE Pervasive Computing\u00a02(1), 46\u201355 (2003)","journal-title":"IEEE Pervasive Computing"},{"issue":"4","key":"55_CR4","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1109\/TKDE.2009.108","volume":"22","author":"M.A. Cheema","year":"2010","unstructured":"Cheema, M.A., Lin, X., Wang, W., Zhang, W., Pei, J.: Probabilistic Reverse Nearest Neighbor Queries on Uncertain Data. IEEE Trans. Knowl. Data Eng.\u00a022(4), 550\u2013564 (2010)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"9","key":"55_CR5","doi-asserted-by":"publisher","first-page":"1112","DOI":"10.1109\/TKDE.2004.46","volume":"16","author":"R. Cheng","year":"2004","unstructured":"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\u00a016(9), 1112\u20131127 (2004)","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"55_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/11957454_23","volume-title":"Privacy Enhancing Technologies","author":"R. Cheng","year":"2006","unstructured":"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.\u00a04258, pp. 393\u2013412. Springer, Heidelberg (2006)"},{"issue":"1","key":"55_CR7","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s004930170002","volume":"21","author":"R. Cole","year":"2001","unstructured":"Cole, R., Ost, K., Schirra, S.: On edge coloring bipartite graphs. Combinatorica\u00a021(1), 5\u201312 (2001)","journal-title":"Combinatorica"},{"key":"55_CR8","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press (2001)"},{"issue":"5","key":"55_CR9","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1142\/S0218195909003076","volume":"19","author":"S. Das","year":"2009","unstructured":"Das, S., Goswani, P.P., Nandy, S.C.: Smallest color-spanning object revised. International Journal of Computational Geometry and Applications\u00a019(5), 457\u2013478 (2009)","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"55_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1007\/978-3-540-87744-8_30","volume-title":"Algorithms - ESA 2008","author":"A. Efrat","year":"2008","unstructured":"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.\u00a05193, pp. 356\u2013367. Springer, Heidelberg (2008)"},{"key":"55_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/978-3-642-14553-7_27","volume-title":"Frontiers in Algorithmics","author":"R. Fleischer","year":"2010","unstructured":"Fleischer, R., Xu, X.: Computing Minimum Diameter Color-Spanning Sets. In: Lee, D.-T., Chen, D.Z., Ying, S. (eds.) FAW 2010. LNCS, vol.\u00a06213, pp. 285\u2013292. Springer, Heidelberg (2010)"},{"key":"55_CR12","unstructured":"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\u2013629 (2005)"},{"key":"55_CR13","doi-asserted-by":"crossref","unstructured":"Goel, A., Kapralov, M., Khanna, S.: Perfect matchings in O(nlogn) time in regular bipartite graphs. In: Proceedings of STOC 2010, pp. 39\u201346 (2010)","DOI":"10.1145\/1806689.1806697"},{"issue":"1","key":"55_CR14","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1112\/jlms\/s1-10.37.26","volume":"10","author":"P. Hall","year":"1935","unstructured":"Hall, P.: On representatives of subsets. J. London Math. Soc.\u00a010(1), 26\u201330 (1935)","journal-title":"J. London Math. Soc."},{"issue":"4","key":"55_CR15","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J. Hopcroft","year":"1973","unstructured":"Hopcroft, J., Karp, R.: An n 5\/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput.\u00a02(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"55_CR16","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/s10878-012-9458-y","volume":"26","author":"W. Ju","year":"2013","unstructured":"Ju, W., Fan, C., Luo, J., Zhu, B., Daescu, O.: On Some Geometric Problems of Color-Spanning Sets. J. of Combinatorial Optimization\u00a026(2), 266\u2013283 (2013)","journal-title":"J. of Combinatorial Optimization"},{"issue":"2","key":"55_CR17","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D. Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput.\u00a011(2), 329\u2013343 (1982)","journal-title":"SIAM J. Comput."},{"key":"55_CR18","doi-asserted-by":"crossref","unstructured":"Mumey, B., Spendlove, K., Zhu, B.: Extending the lifetime of a WSN by partial covers. In: Proceedings of IEEE ICC 2013 (2013)","DOI":"10.1109\/ICC.2013.6654777"},{"key":"55_CR19","unstructured":"Pei, J., Jiang, B., Lin, X., Yuan, Y.: Probabilistic Skylines on Uncertain Data. In: Proc. of VLDB 2007, pp. 15\u201326 (2007)"},{"key":"55_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/3-540-48482-5_9","volume-title":"Advances in Spatial Databases","author":"D. Pfoser","year":"1999","unstructured":"Pfoser, D., Jensen, C.S.: Capturing the uncertainty of moving-objects representations. In: G\u00fcting, R.H., Papadias, D., Lochovsky, F.H. (eds.) SSD 1999. LNCS, vol.\u00a01651, pp. 111\u2013131. Springer, Heidelberg (1999)"},{"key":"55_CR21","doi-asserted-by":"crossref","unstructured":"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.\u00a01399, pp. 310\u2013337. Springer, Heidelberg (1998)","DOI":"10.1007\/BFb0053708"},{"issue":"2","key":"55_CR22","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R. Tarjan","year":"1975","unstructured":"Tarjan, R.: Efficiency of a good but not linear set union algorithm. J. of ACM\u00a022(2), 215\u2013225 (1975)","journal-title":"J. of ACM"},{"key":"55_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1007\/978-3-540-72870-2_29","volume-title":"Algorithmic Aspects in Information and Management","author":"Y. Yang","year":"2007","unstructured":"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.\u00a04508, pp. 306\u2013316. Springer, Heidelberg (2007)"},{"issue":"7","key":"55_CR24","doi-asserted-by":"publisher","first-page":"1041","DOI":"10.1109\/TKDE.2009.137","volume":"22","author":"S.-M. Yuen","year":"2010","unstructured":"Yuen, S.-M., Tao, Y., Xiao, X., Pei, J., Zhang, D.: Superseding Nearest Neighbor Search on Uncertain Spatial Databases. IEEE Trans. Knowl. Data Eng.\u00a022(7), 1041\u20131055 (2010)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"55_CR25","doi-asserted-by":"crossref","unstructured":"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\u2013699 (2009)","DOI":"10.1109\/ICDE.2009.77"},{"key":"55_CR26","first-page":"89","volume":"1","author":"H. Zhang","year":"2005","unstructured":"Zhang, H., Hou, J.C.: Maintaining sensing coverage and connectivity in large sensor networks. Ad Hoc & Sensor Wireless Networks, an Intl J.\u00a01, 89\u2013124 (2005)","journal-title":"Ad Hoc & Sensor Wireless Networks, an Intl J."},{"key":"55_CR27","doi-asserted-by":"crossref","unstructured":"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\u201347 (2009)","DOI":"10.1109\/WiMob.2009.17"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-45030-3_55","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,4]],"date-time":"2019-08-04T16:27:55Z","timestamp":1564936075000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-45030-3_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642450297","9783642450303"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-45030-3_55","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}