{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:57:28Z","timestamp":1725537448453},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642041273"},{"type":"electronic","value":"9783642041280"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04128-0_19","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T14:16:36Z","timestamp":1252937796000},"page":"215-226","source":"Crossref","is-referenced-by-count":0,"title":["Narrow-Shallow-Low-Light Trees with and without Steiner Points"],"prefix":"10.1007","author":[{"given":"Michael","family":"Elkin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shay","family":"Solomon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"7","key":"19_CR1","doi-asserted-by":"publisher","first-page":"890","DOI":"10.1109\/43.391737","volume":"14","author":"C.J. Alpert","year":"1995","unstructured":"Alpert, C.J., Hu, T.C., Huang, J.H., Kahng, A.B., Karger, D.: Prim-Dijkstra tradeoffs for improved performance-driven routing tree design. IEEE Trans. on CAD of Integrated Circuits and Systems\u00a014(7), 890\u2013896 (1995)","journal-title":"IEEE Trans. on CAD of Integrated Circuits and Systems"},{"key":"19_CR2","first-page":"489","volume-title":"27th ACM Symposium on Theory of Computing","author":"S. Arya","year":"1995","unstructured":"Arya, S., Das, G., Mount, D.M., Salowe, J.S., Smid, M.H.M.: Euclidean spanners: short, thin, and lanky. In: 27th ACM Symposium on Theory of Computing, pp. 489\u2013498. ACM Press, New York (1995)"},{"key":"19_CR3","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1145\/93385.93417","volume-title":"9th ACM Symposium on Principles of Distributed Computing","author":"B. Awerbuch","year":"1990","unstructured":"Awerbuch, B., Baratz, A., Peleg, D.: Cost-sensitive analysis of communication protocols. In: 9th ACM Symposium on Principles of Distributed Computing, pp. 177\u2013187. ACM Press, New York (1990)"},{"key":"19_CR4","unstructured":"Awerbuch, B., Baratz, A., Peleg, D.: Efficient Broadcast and Light-Weight Spanners (manuscript) (1991)"},{"issue":"2","key":"19_CR5","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s00454-004-1117-3","volume":"32","author":"T.M. Chan","year":"2004","unstructured":"Chan, T.M.: Euclidean Bounded-Degree Spanning Tree Ratios. Discrete & Computational Geometry\u00a032(2), 177\u2013194 (2004)","journal-title":"Discrete & Computational Geometry"},{"key":"19_CR6","first-page":"170","volume-title":"9th IEEE International Conference on Computer Design: VLSI in Computer & Processors","author":"J. Cong","year":"1991","unstructured":"Cong, J., Kahng, A.B., Robins, G., Sarrafzadeh, M., Wong, C.K.: Performance-Driven Global Routing for Cell Based ICs. In: 9th IEEE International Conference on Computer Design: VLSI in Computer & Processors, pp. 170\u2013173. IEEE press, New York (1991)"},{"issue":"6","key":"19_CR7","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1109\/43.137519","volume":"11","author":"J. Cong","year":"1992","unstructured":"Cong, J., Kahng, A.B., Robins, G., Sarrafzadeh, M., Wong, C.K.: Provably good performance-driven global routing. IEEE Trans. on CAD of Integrated Circuits and Sys.\u00a011(6), 739\u2013752 (1992)","journal-title":"IEEE Trans. on CAD of Integrated Circuits and Sys."},{"key":"19_CR8","first-page":"519","volume-title":"49th IEEE Symposium on Foundations of Computer Science","author":"Y. Dinitz","year":"2008","unstructured":"Dinitz, Y., Elkin, M., Solomon, S.: Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners. In: 49th IEEE Symposium on Foundations of Computer Science, pp. 519\u2013528. EEE Press, New York (2008)"},{"key":"19_CR9","unstructured":"Eppstein, D.: Spanning trees and spanners. Technical report 96\u201316, Dept. of Information and Computer-Science, University of California, Irvine (1996)"},{"key":"19_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/978-3-540-72845-0_21","volume-title":"Experimental Algorithms","author":"M. Farshi","year":"2007","unstructured":"Farshi, M., Gudmundsson, J.: Experimental Study of Geometric t-Spanners: A Running Time Comparison. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol.\u00a04525, pp. 270\u2013284. Springer, Heidelberg (2007)"},{"issue":"2","key":"19_CR11","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1006\/jagm.1997.0862","volume":"24","author":"S.P. Fekete","year":"1997","unstructured":"Fekete, S.P., Khuller, S., Klemmstein, M., Raghavachari, B., Young, N.E.: A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees. J. Algorithms\u00a024(2), 310\u2013324 (1997)","journal-title":"J. Algorithms"},{"key":"19_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1007\/3-540-45706-2_134","volume-title":"Euro-Par 2002. Parallel Processing","author":"M. Gr\u00fcnewald","year":"2002","unstructured":"Gr\u00fcnewald, M., Lukovszki, T., Schindelhauer, C., Volbert, K.: Distributed Maintenance of Resource Efficient Wireless Network Topologies. In: Monien, B., Feldmann, R.L. (eds.) Euro-Par 2002. LNCS, vol.\u00a02400, pp. 935\u2013946. Springer, Heidelberg (2002)"},{"key":"19_CR13","first-page":"220","volume-title":"12th ACM-SIAM Symposium on Discrete Algorithms","author":"A. Gupta","year":"2001","unstructured":"Gupta, A.: Steiner points in tree metrics don\u2019t (really) help. In: 12th ACM-SIAM Symposium on Discrete Algorithms, pp. 220\u2013227. SIAM Press, Philadelphia (2001)"},{"key":"19_CR14","first-page":"243","volume-title":"4th ACM-SIAM Symposium on Discrete Algorithms","author":"S. Khuller","year":"1993","unstructured":"Khuller, S., Raghavachari, B., Young, N.E.: Balancing Minimum Spanning and Shortest Path Trees. In: 4th ACM-SIAM Symposium on Discrete Algorithms, pp. 243\u2013250. ACM Press, New York (1993)"},{"key":"19_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/3-540-48447-7_20","volume-title":"Algorithms and Data Structures","author":"T. Lukovszki","year":"1999","unstructured":"Lukovszki, T.: New Results on Fault Tolerant Geometric Spanners. In: Dehne, F., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1999. LNCS, vol.\u00a01663, pp. 193\u2013204. Springer, Heidelberg (1999)"},{"key":"19_CR16","unstructured":"Lukovszki, T.: New Results on Geometric Spanners and Their Applications. Ph.D thesis, Dept. of Computer-Science, University of Paderborn, Paderborn, Germany (1999)"},{"issue":"9","key":"19_CR17","first-page":"1292","volume":"12","author":"T. Lukovszki","year":"2006","unstructured":"Lukovszki, T., Schindelhauer, C., Volbert, K.: Resource Efficient Maintenance of Wireless Network Topologies. J. UCS\u00a012(9), 1292\u20131311 (2006)","journal-title":"J. UCS"},{"key":"19_CR18","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF02293049","volume":"8","author":"C.L. Monma","year":"1992","unstructured":"Monma, C.L., Suri, S.: Transitions in Geometric Minimum Spanning Trees. Discrete & Computational Geometry\u00a08, 265\u2013293 (1992)","journal-title":"Discrete & Computational Geometry"},{"key":"19_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884","volume-title":"Geometric Spanner Networks","author":"G. Narasimhan","year":"2007","unstructured":"Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007)"},{"issue":"2","key":"19_CR20","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0196-6774(84)90029-4","volume":"5","author":"C.H. Papadimitriou","year":"1984","unstructured":"Papadimitriou, C.H., Vazirani, U.V.: On Two Geometric Problems Related to the Traveling Salesman Problem. J. Algorithms\u00a05(2), 231\u2013246 (1984)","journal-title":"J. Algorithms"},{"key":"19_CR21","unstructured":"Ruppert, J., Seidel, R.: Approximating the d-dimensional complete Euclidean graph. In: 3rd Canadian Conference on Computational Geometry, pp. 207\u2013210 (1991)"},{"key":"19_CR22","first-page":"62","volume-title":"3rd ACM Great Lakes symposium on VLSI","author":"J.S. Salowe","year":"1993","unstructured":"Salowe, J.S., Richards, D.S., Wrege, D.E.: Mixed spanning trees: a technique for performance-driven routing. In: 3rd ACM Great Lakes symposium on VLSI, pp. 62\u201366. ACM Press, New York (1993)"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,19]],"date-time":"2019-01-19T06:06:08Z","timestamp":1547877968000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}