{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T16:32:48Z","timestamp":1781886768610,"version":"3.54.5"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319182629","type":"print"},{"value":"9783319182636","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-18263-6_19","type":"book-chapter","created":{"date-parts":[[2015,4,22]],"date-time":"2015-04-22T14:41:38Z","timestamp":1429713698000},"page":"224-235","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Steiner Trees with Bounded RC-Delay"],"prefix":"10.1007","author":[{"given":"Rudolf","family":"Scheifele","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,4,23]]},"reference":[{"key":"19_CR1","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM 45, 753\u2013782 (1998)","journal-title":"J. ACM"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Boese, K.D., Kahng, A.B., McCoy, B.A., Robins, G.: Fidelity and near-optimality of elmore-based routing constructions. In: IEEE International Conference on Computer Design, pp. 81\u201384 (1993)","DOI":"10.1109\/ICCD.1993.393400"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"Boese, K.D., Kahng, A.B., McCoy, B.A., Robins, G.: Rectilinear steiner trees with minimum elmore delay. In: Proceedings of the 31st Annual Design Automation Conference, pp. 381\u2013386. ACM, New York (1994)","DOI":"10.1145\/196244.196428"},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"1417","DOI":"10.1109\/43.476573","volume":"14","author":"KD Boese","year":"1995","unstructured":"Boese, K.D., Kahng, A.B., McCoy, B.A., Robins, G.: Near-optimal critical sink routing tree constructions. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 14, 1417\u20131436 (1995)","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."},{"key":"19_CR5","doi-asserted-by":"publisher","first-page":"6:1","DOI":"10.1145\/2432622.2432628","volume":"60","author":"J Byrka","year":"2013","unstructured":"Byrka, J., Grandoni, F., Rothvoss, T., Sanit\u00e0, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60, 6:1\u20136:33 (2013)","journal-title":"J. ACM"},{"key":"19_CR6","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1109\/TCAD.2007.907068","volume":"27","author":"C Chu","year":"2008","unstructured":"Chu, C., Wong, Y.C.: FLUTE: fast lookup table based rectilinear steiner minimal tree algorithm for VLSI design. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 27, 70\u201383 (2008)","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."},{"key":"19_CR7","unstructured":"C\u00f3rdova, J., Lee, Y.: A heuristic algorithm for the rectilinear steiner arborescence problem. Technical report, University of Puerto Rico, Computer Science Department (1994)"},{"key":"19_CR8","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"S Dreyfus","year":"1972","unstructured":"Dreyfus, S., Wagner, R.: The steiner problem in graphs. Networks 1, 195\u2013207 (1972)","journal-title":"Networks"},{"key":"19_CR9","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1063\/1.1697872","volume":"19","author":"W Elmore","year":"1948","unstructured":"Elmore, W.: The transient response of damped linear networks with particular regard to wideband amplifiers. J. Appl. Phys. 19, 55\u201363 (1948)","journal-title":"J. Appl. Phys."},{"key":"19_CR10","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear steiner tree problem is NP-complete. SIAM J. Appl. Math. 32, 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"19_CR11","doi-asserted-by":"publisher","first-page":"32:1","DOI":"10.1145\/2442087.2442103","volume":"18","author":"M Gester","year":"2013","unstructured":"Gester, M., M\u00fcller, D., Nieberg, T., Panten, C., Schulte, C., Vygen, J.: BonnRoute: algorithms and data structures for fast and good VLSI routing. ACM Trans. Des. Autom. Electron. Syst. 18, 32:1\u201332:24 (2013)","journal-title":"ACM Trans. Des. Autom. Electron. Syst."},{"key":"19_CR12","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1109\/43.559334","volume":"16","author":"R Gupta","year":"1997","unstructured":"Gupta, R., Tutuianu, B., Pileggi, L.: The elmore delay as a bound for RC trees with generalized input signals. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 16, 95\u2013104 (1997)","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."},{"key":"19_CR13","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/0114025","volume":"14","author":"M Hanan","year":"1966","unstructured":"Hanan, M.: On Steiner\u2019s problem with rectilinear distance. SIAM J. Appl. Math. 14, 255\u2013265 (1966)","journal-title":"SIAM J. Appl. Math."},{"key":"19_CR14","unstructured":"Held, S., Korte, B., Rautenbach, D., Vygen, J.: Combinatorial optimization in VLSI design. In: Combinatorial Optimization: Methods and Applications, pp. 33\u201396. IOS Press, Amsterdam (2011)"},{"key":"19_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/978-3-642-36694-9_20","volume-title":"Integer Programming and Combinatorial Optimization","author":"S Held","year":"2013","unstructured":"Held, S., Rotter, D.: Shallow-light steiner arborescences with vertex delays. In: Goemans, M., Correa, J. (eds.) IPCO 2013. LNCS, vol. 7801, pp. 229\u2013241. Springer, Heidelberg (2013)"},{"key":"19_CR16","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1137\/0130013","volume":"30","author":"F Hwang","year":"1976","unstructured":"Hwang, F.: On steiner minimal trees with rectilinear distance. SIAM J. Appl. Math. 30, 104\u2013114 (1976)","journal-title":"SIAM J. Appl. Math."},{"key":"19_CR17","unstructured":"Kadodi, T.: Steiner routing based on elmore delay model for minimizing maximum propagation delay. Master\u2019s thesis, Japan Advanced Institute of Science and Technology (1999)"},{"key":"19_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2363-2","volume-title":"On Optimal Interconnections for VLSI","author":"A Kahng","year":"1995","unstructured":"Kahng, A., Robins, G.: On Optimal Interconnections for VLSI. Kluwer Academic Publishers, Boston (1995)"},{"key":"19_CR19","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R Karp","year":"1972","unstructured":"Karp, R.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"19_CR20","unstructured":"Khuller, S., Raghavachari, B., Young, N.: Balancing minimum spanning and shortest path trees. In: Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 243\u2013250. Society for Industrial and Applied Mathematics, Philadelphia (1993)"},{"key":"19_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24488-9","volume-title":"Combinatorial Optimization: Theory and Algorithms","author":"B Korte","year":"2012","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, 5th edn. Springer, Heidelberg (2012)","edition":"5"},{"key":"19_CR22","unstructured":"Peyer, S.: Elmore-delay-optimale Steinerb\u00e4ume and VLSI-Design. Diploma\u2019s thesis (in german), Research Institute for Discrete Mathematics, University of Bonn (2000)"},{"key":"19_CR23","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/S0166-218X(03)00445-1","volume":"136","author":"S Peyer","year":"2004","unstructured":"Peyer, S., Zachariasen, M., J\u00f8rgensen, D.G.: Delay-related secondary objectives for rectilinear steiner minimum trees. Discret. Appl. Math. 136, 271\u2013298 (2004)","journal-title":"Discret. Appl. Math."},{"key":"19_CR24","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/BF01758762","volume":"7","author":"S Rao","year":"1992","unstructured":"Rao, S., Sadayappan, P., Hwang, F., Shor, P.: The rectilinear steiner arborescence problem. Algorithmica 7, 277\u2013288 (1992)","journal-title":"Algorithmica"},{"key":"19_CR25","doi-asserted-by":"crossref","unstructured":"Rao, S.B., Smith, W.D.: Approximating geometrical graphs via \u201cspanners\u201d and \u201cbanyans\u201d. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 540\u2013550. ACM, New York (1998)","DOI":"10.1145\/276698.276868"},{"key":"19_CR26","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1109\/TCAD.1983.1270037","volume":"2","author":"J Rubinstein","year":"1983","unstructured":"Rubinstein, J., Penfield, P., Horowitz, M.A.: Signal delay in RC tree networks. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 2, 202\u2013211 (1983)","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."},{"key":"19_CR27","unstructured":"Scheifele, R.: Steiner trees with bounded elmore delay. Master\u2019s thesis, Research Institute for Discrete Mathematics, University of Bonn (2013)"},{"key":"19_CR28","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1137\/S0097539704371353","volume":"35","author":"W Shi","year":"2005","unstructured":"Shi, W., Su, C.: The rectilinear steiner arborescence problem is NP-complete. SIAM J. Comput. 35, 729\u2013740 (2005)","journal-title":"SIAM J. Comput."},{"key":"19_CR29","doi-asserted-by":"publisher","first-page":"1075","DOI":"10.1016\/j.ipl.2011.08.005","volume":"111","author":"J Vygen","year":"2011","unstructured":"Vygen, J.: Faster algorithm for optimum steiner trees. Inf. Process. Lett. 111, 1075\u20131079 (2011)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-18263-6_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T21:03:53Z","timestamp":1747947833000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-18263-6_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319182629","9783319182636"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-18263-6_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"23 April 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}