{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T05:34:26Z","timestamp":1740548066086,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540230250"},{"type":"electronic","value":"9783540301400"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30140-0_9","type":"book-chapter","created":{"date-parts":[[2010,9,19]],"date-time":"2010-09-19T01:31:13Z","timestamp":1284859873000},"page":"77-88","source":"Crossref","is-referenced-by-count":0,"title":["Labeling Smart Dust"],"prefix":"10.1007","author":[{"given":"Vikas","family":"Bansal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Friedhelm Meyer auf","family":"der Heide","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Sohler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Appel, M., Russo, R.: The Maximum Vertex Degree of a Graph on Uniform Points in [0, 1] d . Adv. Appl. Prob., 567\u2013581 (1997)","key":"9_CR1","DOI":"10.1017\/S000186780002824X"},{"doi-asserted-by":"crossref","unstructured":"Appel, M., Russo, R.: The connectivity of a graph on uniform points in [0, 1] d . Statistics and Probability Letters\u00a060, 351\u2013357","key":"9_CR2","DOI":"10.1016\/S0167-7152(02)00233-X"},{"doi-asserted-by":"crossref","unstructured":"Banderier, C., Mehlhorn, K., Beier, R.: Smoothed Analysis of Three Combinatorial Problems. In: Proc. of the 28th International Symposium on Mathematical Foundations of Computer Science, pp. 198\u2013207 (2003)","key":"9_CR3","DOI":"10.1007\/978-3-540-45138-9_14"},{"doi-asserted-by":"crossref","unstructured":"Becchetti, L., Leonardi, S., Marchetti-Spaccamela, A., Sch\u00e4fer, G., Vredeveld, T.: Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm. In: Proc. of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 462\u2013471 (2003)","key":"9_CR4","DOI":"10.1109\/SFCS.2003.1238219"},{"doi-asserted-by":"crossref","unstructured":"Beier, R., V\u00f6cking, B.: Typical Properties of Winners and Losers in Discrete Optimization. In: Proc. of the 36th Annual ACM Symposium on Theory of Computing, pp. 343\u2013352 (2004)","key":"9_CR5","DOI":"10.1145\/1007352.1007409"},{"unstructured":"Blum, A., Dunagan, J.: Smoothed analysis of the perceptron algorithm for linear programming. In: Proc. of the 13th annual ACM-SIAM Symposium on Discrete algorithms, pp. 905\u2013914 (2002)","key":"9_CR6"},{"doi-asserted-by":"crossref","unstructured":"Damerow, V., Meyer auf der Heide, F., R\u00e4cke, H., Scheideler, C., Sohler, C.: Smoothed Motion Complexity. In: Proc. of the 11th European Symposium on Algorithms, pp. 161\u2013171 (2003)","key":"9_CR7","DOI":"10.1007\/978-3-540-39658-1_17"},{"key":"9_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/3-540-49543-6_23","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"J. Diaz","year":"1998","unstructured":"Diaz, J., Petit, J., Serna, M.: Random Geometric Problems on [0, 1]2. In: Rolim, J.D.P., Serna, M., Luby, M. (eds.) RANDOM 1998. LNCS, vol.\u00a01518, pp. 294\u2013306. Springer, Heidelberg (1998)"},{"unstructured":"Doddi, S., Marathe, M.V., Mirzaian, A., Moret, B.M.E., Zhu, B.: Map labeling and its generalizations. In: Proc. of the 8th ACM-SIAM Symposium on Discrete Algorithms, pp. 148\u2013157 (1997)","key":"9_CR9"},{"doi-asserted-by":"crossref","unstructured":"Formann, M., Wagner, F.: A packing problem with applications to lettering of maps. In: Proc. of the 7th Annuual ACM Symposium on Computational Geometry, pp. 281\u2013288 (1991)","key":"9_CR10","DOI":"10.1145\/109648.109680"},{"doi-asserted-by":"crossref","unstructured":"Goel, A., Rai, S., Krishnamachari, B.: Sharp thresholds for monotone properties in random geometric graphs. In: Proc. of the 36th Annual ACM Symposium on Theory of Computing, pp. 580\u2013586 (2004)","key":"9_CR11","DOI":"10.1145\/1007352.1007441"},{"doi-asserted-by":"crossref","unstructured":"Gupta, P., Kumar, P.: Critical Power for Asymptotic Connectivity in Wireless Networks. In: McEneaney, W.M., Yin, G., Zhang, Q. (eds.) Stochastic Analysis, Control, Optimization and Applications:AVolume in Honor of W. H. Fleming (1998)","key":"9_CR12","DOI":"10.1007\/978-1-4612-1784-8_33"},{"key":"9_CR13","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0925-7721(99)00005-X","volume":"13","author":"M. Kreveld van","year":"1999","unstructured":"van Kreveld, M., Strijk, T., Wolff, A.: Point labeling with sliding labels. TR Comput. Geom. Theory Appl.\u00a013, 21\u201347 (1999)","journal-title":"TR Comput. Geom. Theory Appl."},{"doi-asserted-by":"crossref","unstructured":"Kucera, L., Mehlhorn, K., Preis, B., Schwarzenecker, E.: Exact algorithms for a geometric packing problem. In: Proc. 10th Symposium on Theoretical Aspects in Computer Science, pp. 317\u2013322 (1993)","key":"9_CR14","DOI":"10.1007\/3-540-56503-5_32"},{"issue":"2","key":"9_CR15","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M","volume":"13","author":"D. Dubhashi","year":"1998","unstructured":"Dubhashi, D., Ranjan, D.: Balls and bins: a study in negative dependence. Random Structures and Algorithms\u00a013(2), 99\u2013124 (1998)","journal-title":"Random Structures and Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Meguerdichian, S., Koushanfar, F., Potkonjak, M., Srivastava, M.B.: Coverage Problems in wireless ad-hoc sensor networks. In: Proc. of INFOCOM 2001, pp. 1380\u20131387 (2001)","key":"9_CR16","DOI":"10.1109\/INFCOM.2001.916633"},{"key":"9_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69672-5","volume-title":"Data Structures and Algorithms 1: Sorting and Searching","author":"K. Mehlhorn","year":"1984","unstructured":"Mehlhorn, K.: Data Structures and Algorithms 1: Sorting and Searching. Springer, Heidelberg (1984)"},{"unstructured":"Muthukrishnan, S., Pandurangan, G.: The Bin-Covering Technique for Thresholding Random Geometric Graph Properties. DIMACS Technical Report (2003)","key":"9_CR18"},{"key":"9_CR19","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1002\/(SICI)1098-2418(199909)15:2<145::AID-RSA2>3.0.CO;2-G","volume":"15","author":"M. Penrose","year":"1999","unstructured":"Penrose, M.: On k-Connectivity for a Geometric Random Graph. Random Structures and Algorithms\u00a015, 145\u2013164 (1999)","journal-title":"Random Structures and Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Qin, Z., Zhu, B.: AFactor-2 Approximation for Labeling Points with Maximum Sliding Labels. In: Proc. of the 8th ScandinavianWorkshop on Algorithm Theory, pp. 100\u2013109 (2002)","key":"9_CR20","DOI":"10.1007\/3-540-45471-3_11"},{"doi-asserted-by":"crossref","unstructured":"Spielman, D., Teng, S.: Smoothed Analysis of Algorithms: Why The Simplex Algorithm Usually Takes Polynomial Time. In: Proc. of the 33rd Annual ACM Symposium on Theory of Computing, pp. 296\u2013305 (2001)","key":"9_CR21","DOI":"10.1145\/380752.380813"},{"doi-asserted-by":"crossref","unstructured":"Wagner, F., Wolff, A.: Map labeling heuristics: Provably good and practically useful. Technical Report B 95-04, Institut f\u00fcr Informatik, Freie Universit\u00e4t Berlin (April 1995)","key":"9_CR22","DOI":"10.1145\/220279.220291"},{"unstructured":"Wolff, A.: The Map-Labeling Bibliography, http:\/\/i11www.ira.uka.de\/map-labeling\/bibliography\/","key":"9_CR23"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30140-0_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T22:38:46Z","timestamp":1740523126000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30140-0_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540230250","9783540301400"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30140-0_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}