{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,6,5]],"date-time":"2023-06-05T03:10:07Z","timestamp":1685934607502},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,2,3]],"date-time":"2011-02-03T00:00:00Z","timestamp":1296691200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2012,7]]},"DOI":"10.1007\/s10878-010-9319-5","type":"journal-article","created":{"date-parts":[[2011,2,2]],"date-time":"2011-02-02T20:07:10Z","timestamp":1296677230000},"page":"15-31","source":"Crossref","is-referenced-by-count":0,"title":["Shifting strategy for geometric graphs without\u00a0geometry"],"prefix":"10.1007","volume":"24","author":[{"given":"Imran A.","family":"Pirwani","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,2,3]]},"reference":[{"issue":"5","key":"9319_CR1","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora S (1998) Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J ACM 45(5):753\u2013782","journal-title":"J ACM"},{"key":"9319_CR2","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/978-3-540-27820-7_5","volume-title":"ALGOSENSORS \u201904: first international workshop on algorithmic aspects of wireless sensor networks","author":"J Aspnes","year":"2004","unstructured":"Aspnes J, Goldenberg DK, Yang YR (2004) On the computational complexity of sensor network localization. In: ALGOSENSORS \u201904: first international workshop on algorithmic aspects of wireless sensor networks, Turku, Finland. Springer, Berlin, pp 32\u201344"},{"issue":"1","key":"9319_CR3","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B Baker","year":"1994","unstructured":"Baker B (1994) Approximation algorithms for np-complete problems on planar graphs. J ACM 41(1):153\u2013180","journal-title":"J ACM"},{"key":"9319_CR4","doi-asserted-by":"crossref","unstructured":"Bil\u00f2 V, Caragiannis I, Kaklamanis C, Kanellopoulos P (2005) Geometric clustering to minimize the sum of cluster sizes. In: ESA, pp\u00a0460\u2013471","DOI":"10.1007\/11561071_42"},{"issue":"1\u20132","key":"9319_CR5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0925-7721(97)00014-X","volume":"9","author":"H Breu","year":"1998","unstructured":"Breu H, Kirkpatrick DG (1998) Unit disk graph recognition is NP-hard. Comput Geom Theory Appl 9(1\u20132):3\u201324","journal-title":"Comput Geom Theory Appl"},{"key":"9319_CR6","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1145\/1062689.1062713","volume-title":"MobiHoc \u201905: proceedings of the 6th ACM international symposium on mobile ad hoc networking and computing","author":"J Bruck","year":"2005","unstructured":"Bruck J, Gao J, Jiang A (2005) Localization and routing in sensor networks by local angle information. In: MobiHoc \u201905: proceedings of the 6th ACM international symposium on mobile ad hoc networking and computing. ACM, New York, pp 181\u2013192"},{"key":"9319_CR7","doi-asserted-by":"crossref","unstructured":"Bulusu N, Heidemann J, Estrin D (2000) GPS-less low cost outdoor localization for very small devices","DOI":"10.1109\/98.878533"},{"key":"9319_CR8","doi-asserted-by":"crossref","unstructured":"Chalermsook P, Chuzhoy J (2009) Maximum independent set of rectangles. In: SODA, pp\u00a0892\u2013901","DOI":"10.1137\/1.9781611973068.97"},{"issue":"2","key":"9319_CR9","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/S0196-6774(02)00294-8","volume":"46","author":"TM Chan","year":"2003","unstructured":"Chan TM (2003) Polynomial-time approximation schemes for packing and piercing fat objects. J Algorithms 46(2):178\u2013189","journal-title":"J Algorithms"},{"key":"9319_CR10","doi-asserted-by":"crossref","unstructured":"Chan TM, Har-Peled S (2009) Approximation algorithms for maximum independent set of pseudo-disks. In: SoCG","DOI":"10.1145\/1542362.1542420"},{"key":"9319_CR11","doi-asserted-by":"crossref","unstructured":"Chintalapudi K, Govindan R, Sukhatme G, Dhariwal A (2004) Ad-hoc localization using ranging and sectoring. In: INFOCOM","DOI":"10.1109\/INFCOM.2004.1354685"},{"key":"9319_CR12","unstructured":"Dhandapani R (2008) Greedy drawings of triangulations. In: SODA, pp\u00a0102\u2013111"},{"key":"9319_CR13","unstructured":"Erlebach T, van Leeuwen EJ (2008) Approximating geometric coverage problems. In: SODA, pp\u00a01267\u20131276"},{"issue":"6","key":"9319_CR14","doi-asserted-by":"crossref","first-page":"1302","DOI":"10.1137\/S0097539702402676","volume":"34","author":"T Erlebach","year":"2005","unstructured":"Erlebach T, Jansen K, Seidel E (2005) Polynomial-time approximation schemes for geometric intersection graphs. SIAM J Comput 34(6):1302\u20131323","journal-title":"SIAM J Comput"},{"key":"9319_CR15","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol J, Rao SB, Talwar K (2003) A tight bound on approximating arbitrary metrics by tree metrics. In: STOC, pp\u00a0448\u2013455","DOI":"10.1145\/780542.780608"},{"key":"9319_CR16","doi-asserted-by":"crossref","unstructured":"Flury R, Pemmaraju SV, Wattenhofer R (2009) Greedy routing with bounded stretch. In: INFOCOM","DOI":"10.1109\/INFCOM.2009.5062093"},{"key":"9319_CR17","doi-asserted-by":"crossref","unstructured":"Gibson M, Kanade G, Krohn E, Pirwani IA, Varadarajan KR (2008) On metric clustering to minimize the sum of radii. In: SWAT, pp\u00a0282\u2013293","DOI":"10.1007\/978-3-540-69903-3_26"},{"key":"9319_CR18","unstructured":"Goodrich MT, Strash D (2009) Succinct greedy geometric routing in the Euclidean plane. In: ISAAC, pp\u00a0781\u2013791"},{"issue":"1","key":"9319_CR19","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum DS, Maass W (1985) Approximation schemes for covering and packing problems in image processing and VLSI. J ACM 32(1):130\u2013136","journal-title":"J ACM"},{"key":"9319_CR20","doi-asserted-by":"crossref","unstructured":"Hunt HB III, Marathe MV, Radhakrishnan V, Ravi SS, Rosenkrantz DJ, Stearns RE (1994) Approximation schemes using l-reductions. In: FSTTCS, pp\u00a0342\u2013353","DOI":"10.1007\/3-540-58715-2_136"},{"issue":"2","key":"9319_CR21","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"HB Hunt III","year":"1998","unstructured":"Hunt HB III, Marathe MV, Radhakrishnan V, Ravi SS, Rosenkrantz DJ, Stearns RE (1998) Nc-approximation schemes for np- and pspace-hard problems for geometric graphs. J Algorithms 26(2):238\u2013274","journal-title":"J Algorithms"},{"issue":"5","key":"9319_CR22","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1007\/s00493-007-2183-y","volume":"27","author":"R Krauthgamer","year":"2007","unstructured":"Krauthgamer R, Lee JR (2007) The intrinsic dimensionality of graphs. Combinatorica 27(5):551\u2013585","journal-title":"Combinatorica"},{"key":"9319_CR23","doi-asserted-by":"crossref","unstructured":"Kuhn F, Moscibroda T, Nieberg T, Wattenhofer R (2005a) Fast deterministic distributed maximal independent set computation on growth-bounded graphs. In: DISC, pp\u00a0273\u2013287","DOI":"10.1007\/11561927_21"},{"key":"9319_CR24","doi-asserted-by":"crossref","unstructured":"Kuhn F, Moscibroda T, Wattenhofer R (2005b) On the locality of bounded growth. In: PODC, pp\u00a060\u201368","DOI":"10.1145\/1073814.1073826"},{"key":"9319_CR25","doi-asserted-by":"crossref","unstructured":"Kuhn F, Nieberg T, Moscibroda T, Wattenhofer R (2005c) Local approximation schemes for ad hoc and sensor networks. In: DIALM-POMC, pp\u00a097\u2013103","DOI":"10.1145\/1080810.1080827"},{"key":"9319_CR26","unstructured":"Kuhn F, Moscibroda T, O\u2019Dell R, Wattenhofer M, Wattenhofer R (2010) Virtual coordinates for ad hoc and sensor networks. Personal communication"},{"issue":"4","key":"9319_CR27","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1016\/j.comnet.2004.08.012","volume":"47","author":"N Lev-Tov","year":"2005","unstructured":"Lev-Tov N, Peleg D (2005) Polynomial time approximation schemes for base station coverage with minimum total radii. Comput Netw 47(4):489\u2013501","journal-title":"Comput Netw"},{"key":"9319_CR28","doi-asserted-by":"crossref","unstructured":"Marx D (2005) Efficient approximation schemes for geometric problems? In: ESA, pp\u00a0448\u2013459","DOI":"10.1007\/11561071_41"},{"key":"9319_CR29","doi-asserted-by":"crossref","unstructured":"Moitra A, Leighton T (2008) Some results on greedy embeddings in metric spaces. In: FOCS, pp\u00a0337\u2013346","DOI":"10.1109\/FOCS.2008.18"},{"key":"9319_CR30","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/3-540-36978-3_22","volume-title":"IPSN \u201903: proceedings of the second international symposium on information processing in sensor networks","author":"R Nagpal","year":"2003","unstructured":"Nagpal R, Shrobe HE, Bachrach J (2003) Organizing a global coordinate system from local information on an ad hoc sensor network. In: IPSN \u201903: proceedings of the second international symposium on information processing in sensor networks. ACM, New York, pp 333\u2013348"},{"key":"9319_CR31","unstructured":"Nieberg T, Hurink J (2005) A PTAS for the minimum dominating set problem in unit disk graphs. In: WAOA, pp\u00a0296\u2013306"},{"key":"9319_CR32","doi-asserted-by":"crossref","unstructured":"Nieberg T, Hurink J, Kern W (2004) A robust PTAS for maximum weight independent sets in unit disk graphs. In: WG, pp\u00a0214\u2013221","DOI":"10.1007\/978-3-540-30559-0_18"},{"issue":"4","key":"9319_CR33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1383369.1383380","volume":"4","author":"T Nieberg","year":"2008","unstructured":"Nieberg T, Hurink J, Kern W (2008) Approximation schemes for wireless networks. ACM Trans Algorithms 4(4):1\u201317","journal-title":"ACM Trans Algorithms"},{"issue":"1","key":"9319_CR34","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.tcs.2005.06.022","volume":"344","author":"CH Papadimitriou","year":"2005","unstructured":"Papadimitriou CH, Ratajczak D (2005) On a conjecture related to geometric routing. Theor Comput Sci 344(1):3\u201314","journal-title":"Theor Comput Sci"},{"key":"9319_CR35","unstructured":"Pemmaraju SV, Pirwani IA (2007) Good quality virtual realization of unit ball graphs. In: ESA, pp\u00a0311\u2013322"},{"key":"9319_CR36","doi-asserted-by":"crossref","unstructured":"Pirwani IA, Salavatipour MR (2010) A weakly robust PTAS for minimum clique partition in unit disk graphs. In: SWAT","DOI":"10.1007\/978-3-642-13731-0_19"},{"key":"9319_CR37","first-page":"460","volume-title":"SODA \u201901: proceedings of the twelfth annual ACM-SIAM symposium on discrete algorithms","author":"V Raghavan","year":"2001","unstructured":"Raghavan V, Spinrad J (2001) Robust algorithms for restricted domains. In: SODA \u201901: proceedings of the twelfth annual ACM-SIAM symposium on discrete algorithms. Society for Industrial and Applied Mathematics, Philadelphia, pp 460\u2013467"},{"key":"9319_CR38","doi-asserted-by":"crossref","unstructured":"Schneider J, Wattenhofer R (2008) A log-star distributed maximal independent set algorithm for growth-bounded graphs. In: PODC, pp\u00a035\u201344","DOI":"10.1145\/1400751.1400758"},{"key":"9319_CR39","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1145\/1007352.1007399","volume-title":"STOC","author":"K Talwar","year":"2004","unstructured":"Talwar K (2004) Bypassing the embedding: algorithms for low dimensional metrics. In: STOC. ACM, New York, pp 281\u2013290"},{"key":"9319_CR40","doi-asserted-by":"crossref","unstructured":"Whitehouse K, Culler DE (2002) Calibration as parameter estimation in sensor networks. In: WSNA, pp\u00a059\u201367","DOI":"10.1145\/570738.570747"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-010-9319-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-010-9319-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-010-9319-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,5]],"date-time":"2023-06-05T02:47:26Z","timestamp":1685933246000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-010-9319-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,2,3]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["9319"],"URL":"https:\/\/doi.org\/10.1007\/s10878-010-9319-5","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,2,3]]}}}