{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,3]],"date-time":"2025-11-03T22:56:36Z","timestamp":1762210596435,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540260523"},{"type":"electronic","value":"9783540320739"}],"license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11429647_9","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T18:18:25Z","timestamp":1279045105000},"page":"89-98","source":"Crossref","is-referenced-by-count":5,"title":["Divide and Conquer Is Almost Optimal for the Bounded-Hop MST Problem on Random Euclidean Instances"],"prefix":"10.1007","author":[{"given":"Andrea E. F.","family":"Clementi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miriam","family":"Di Ianni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angelo","family":"Monti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Massimo","family":"Lauria","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianluca","family":"Rossi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Riccardo","family":"Silvestri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1111\/j.1475-3995.1999.tb00176.x","volume":"6","author":"L. Alfandari","year":"1999","unstructured":"Alfandari, L., Paschos, V.T.: Approximating minimum spanning tree of depth 2. Intl. Trans. In Op. Res.\u00a06, 607\u2013622 (1999)","journal-title":"Intl. Trans. In Op. Res."},{"key":"9_CR2","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.orl.2004.05.005","volume":"33","author":"E. Althaus","year":"2005","unstructured":"Althaus, E., Funke, S., Har-Peled, S., Koenemann, J., Ramos, E.A., Skutella, M.: Approximation k-hop minimum-spanning trees. Operations Research Letters\u00a033, 115\u2013120 (2005)","journal-title":"Operations Research Letters"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Raghavan, P., Rao, S.: Approximation schemes for Euclidean k-medians and related problems. In: Proc. 30th ACM Symposium on Theory of Computing, pp. 106\u2013113 (1998)","DOI":"10.1145\/276698.276718"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Bala, K., Petropoulos, K., Stern, T.E.: Multicasting in a Linear Lightwave Network. In: Proc. of INFOCOM, pp. 1350\u20131358 (1993)","DOI":"10.1109\/INFCOM.1993.253399"},{"key":"9_CR5","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1287\/ijoc.4.2.192","volume":"4","author":"A. Balakrishnan","year":"1992","unstructured":"Balakrishnan, A., Altinkemer, K.: Using a hop-constrained model to generate alternative communication network design. ORSA Journal of Computing\u00a04, 147\u2013159 (1992)","journal-title":"ORSA Journal of Computing"},{"issue":"4","key":"9_CR6","first-page":"110","volume":"16","author":"A. Bookstein","year":"1996","unstructured":"Bookstein, A., Klein, S.T.: Compression of Correlated Bit-Vectors. Information Systems\u00a016(4), 110\u2013118 (1996)","journal-title":"Information Systems"},{"key":"9_CR7","unstructured":"Chou, R., Johnson, T.: Distributed Operating Systems and Algorithms. Addison-Wesley, Reading (1997)"},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"Chudak, F.A.: Improved approximation algorithms for uncapacitated facility location problem. In: Proc. of the 6th Conference on Integer Programming and Combinatorial Optimization (1998)","DOI":"10.1007\/3-540-69346-7_14"},{"key":"9_CR9","unstructured":"Clementi, A.E.F., Di Ianni, M., Monti, A., Rossi, G., Silvestri, R.: Experimental Analysis of Practically Efficient Algorithms for Bounded-Hop Accumulation in Ad-Hoc Wireless Networks. In: Proc. of the IEEE IPDPS-WMAN (2005) (to appear)"},{"key":"9_CR10","unstructured":"Ephremides, A., Nguyen, G.D., Wieselthier, J.E.: On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks. In: Proc. of the 19th INFOCOM, pp. 585\u2013594 (2000)"},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"959","DOI":"10.1016\/0305-0548(94)00074-I","volume":"22","author":"L. Gouveia","year":"1995","unstructured":"Gouveia, L.: Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with hop constraints. Computers and Operations Research\u00a022, 959\u2013970 (1995)","journal-title":"Computers and Operations Research"},{"key":"9_CR12","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/0377-2217(95)00090-9","volume":"95","author":"L. Gouveia","year":"1996","unstructured":"Gouveia, L.: Multicommodity flow models for spanning trees with hop constraints. European Journal of Operational Research\u00a095, 178\u2013190 (1996)","journal-title":"European Journal of Operational Research"},{"key":"9_CR13","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1016\/S0377-2217(00)00143-0","volume":"132","author":"L. Gouveia","year":"2001","unstructured":"Gouveia, L., Requejo, C.: A new relaxation approach for the hop-constrain minimum spanning tree problem. European Journal of Operational Research\u00a0132, 539\u2013552 (2001)","journal-title":"European Journal of Operational Research"},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"S. Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. Journal of Algorithms\u00a031, 228\u2013248 (1999)","journal-title":"Journal of Algorithms"},{"key":"9_CR15","unstructured":"Haenggi, M.: Twelve Reasons not to Route over Many Short Hops. In: Proc. IEEE Vehicular Technology Conference (VTC 2004 Fall), Los Angeles, CA (September 2004)"},{"key":"9_CR16","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/S0166-218X(99)00111-0","volume":"93","author":"G. Kortsarz","year":"1999","unstructured":"Kortsarz, G., Peleg, D.: Approximating the weight of shallow Steiner trees. Discrete Applied Mathematics\u00a093, 265\u2013285 (1999)","journal-title":"Discrete Applied Mathematics"},{"key":"9_CR17","unstructured":"Korupolu, M.R., Plaxton, C.G., Rajaraman, R.: Analysis of a Local Search Heuristic for Facility Location Problems. In: Proc. of the 9th annual ACM-SIAM Symposium on Discrete algorithms, pp. 1\u201310 (1998)"},{"key":"9_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/3-540-45753-4_20","volume-title":"Proc. of APPROX 2002","author":"M. Mahdian","year":"2002","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: A 1.52-approximation algorithm for the uncapacitated facility location problem. In: Proc. of APPROX 2002. LNCS, vol.\u00a02462, pp. 229\u2013242. Springer, Heidelberg (2002)"},{"key":"9_CR19","doi-asserted-by":"crossref","unstructured":"McDiarmid, C.J.H.: On the method of bounded differences. In: Siemons, J. (ed.) Surveys in Combinatorics: Invited Papers at the 12th British Combinatorial Conference, London. Mathematical Society Lecture Notes Series, vol.\u00a0141, pp. 148\u2013188 (1989)","DOI":"10.1017\/CBO9781107359949.008"},{"key":"9_CR20","volume-title":"Randomized Algorithms","author":"P. Raghavan","year":"1995","unstructured":"Raghavan, P., Motwani, R.: Randomized Algorithms. Cambridge Univ. Press, Cambridge (1995)"},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"Raidl, G.R., Julstrom, B.A.: Greedy Heuristics and an Evolutionary Algorithm for the Bounded-Diameter Minimum Spanning Tree Problem. In: Proc. of the 2003 ACM Symposium on Applied Computing, pp. 747\u2013752 (2003)","DOI":"10.1145\/952532.952678"},{"issue":"1","key":"9_CR22","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1145\/58564.59295","volume":"7","author":"K. Raymond","year":"1989","unstructured":"Raymond, K.: A Tree-Based Algorithm for Distributed Mutual Exclusion. ACM Transactions on Computer Systems\u00a07(1), 61\u201377 (1989)","journal-title":"ACM Transactions on Computer Systems"},{"key":"9_CR23","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Tardos, E., Aardal, K.: Approximation algorithms for facility location problems. In: Proc. of the 29-th Annual ACM Symposium on Theory of Computing, pp. 265\u2013274 (1997)","DOI":"10.1145\/258533.258600"},{"key":"9_CR24","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1023\/A:1018967121276","volume":"86","author":"S. Voss","year":"1999","unstructured":"Voss, S.: The steiner tree problem with hop constraint. Annals of Operations Research\u00a086, 321\u2013345 (1999)","journal-title":"Annals of Operations Research"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11429647_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T21:52:42Z","timestamp":1740261162000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11429647_9"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540260523","9783540320739"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/11429647_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}