{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T15:41:05Z","timestamp":1780674065629,"version":"3.54.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,4,27]],"date-time":"2016-04-27T00:00:00Z","timestamp":1461715200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,5]]},"DOI":"10.1007\/s00453-016-0149-4","type":"journal-article","created":{"date-parts":[[2016,4,28]],"date-time":"2016-04-28T12:11:33Z","timestamp":1461845493000},"page":"86-109","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Steiner Trees with Bounded RC-Delay"],"prefix":"10.1007","volume":"78","author":[{"given":"Rudolf","family":"Scheifele","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,4,27]]},"reference":[{"key":"149_CR1","doi-asserted-by":"crossref","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":"149_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":"149_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":"149_CR4","doi-asserted-by":"crossref","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":"149_CR5","doi-asserted-by":"crossref","unstructured":"Boese, K.D., Kahng, A.B., Robins, G.: High-Performance routing trees with identified critical sinks. In: Proceedings of the 30th International Design Automation Conference, pp. 182\u2013187 (1993)","DOI":"10.1145\/157485.164662"},{"key":"149_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-13915-9","volume-title":"Optimal Interconnection Trees in the Plane","author":"M Brazil","year":"2015","unstructured":"Brazil, M., Zachariasen, M.: Optimal Interconnection Trees in the Plane. Springer, Berlin (2015)"},{"key":"149_CR7","doi-asserted-by":"crossref","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":"149_CR8","volume-title":"IC Interconnect Analysis","author":"M Celik","year":"2002","unstructured":"Celik, M., Pileggi, L., Odabasioglu, A.: IC Interconnect Analysis. Kluwer, Boston (2002)"},{"key":"149_CR9","doi-asserted-by":"crossref","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":"149_CR10","doi-asserted-by":"crossref","unstructured":"Cong, J., Leung, K.S., Zhou, D.: Performance-driven interconnect design based on distributed rc delay model. In: Proceedings of the 30th International Design Automation Conference, pp. 606\u2013611. ACM (1993)","DOI":"10.1145\/157485.165065"},{"key":"149_CR11","unstructured":"C\u00f3rdova, J., Lee, Y.: A Heuristic Algorithm for the Rectilinear Steiner Arborescence Problem. Tech. rep., University of Puerto Rico, Computer Science Department (1994)"},{"key":"149_CR12","doi-asserted-by":"crossref","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":"149_CR13","doi-asserted-by":"crossref","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":"149_CR14","doi-asserted-by":"crossref","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":"149_CR15","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1990","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Company, New York (1990)"},{"key":"149_CR16","doi-asserted-by":"crossref","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":"149_CR17","doi-asserted-by":"crossref","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":"149_CR18","doi-asserted-by":"crossref","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":"149_CR19","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":"149_CR20","doi-asserted-by":"crossref","unstructured":"Held, S., Rotter, D.: Shallow-light Steiner arborescences with vertex delays. In: Proceedings of the 16th International Conference on Integer Programming and Combinatorial Optimization, pp. 229\u2013241. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-36694-9_20"},{"key":"149_CR21","doi-asserted-by":"crossref","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":"149_CR22","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":"149_CR23","doi-asserted-by":"crossref","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, Boston (1995)"},{"key":"149_CR24","doi-asserted-by":"crossref","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":"149_CR25","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":"149_CR26","doi-asserted-by":"crossref","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":"149_CR27","first-page":"333","volume-title":"Building Bridges\u2014Between Mathematics and Computer Science","author":"B Korte","year":"2008","unstructured":"Korte, B., Vygen, K.: Combinatorial problems in chip design. In: Gr\u00f6tschel, M., Katona, G.O.H. (eds.) Building Bridges\u2014Between Mathematics and Computer Science, pp. 333\u2013368. Springer, Berlin (2008)"},{"key":"149_CR28","unstructured":"Peyer, S.: Elmore-Delay-optimale Steinerb\u00e4ume im VLSI-Design. Diploma\u2019s Thesis (in german), Research Institute for Discrete Mathematics, University of Bonn (2000)"},{"key":"149_CR29","doi-asserted-by":"crossref","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. Discrete Appl. Math. 136, 271\u2013298 (2004)","journal-title":"Discrete Appl. Math."},{"key":"149_CR30","doi-asserted-by":"crossref","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":"149_CR31","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":"149_CR32","doi-asserted-by":"crossref","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":"149_CR33","unstructured":"Scheifele, R.: Steiner Trees with Bounded Elmore Delay. Master\u2019s Thesis, Research Institute for Discrete Mathematics, University of Bonn (2013)"},{"key":"149_CR34","doi-asserted-by":"crossref","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":"149_CR35","doi-asserted-by":"crossref","unstructured":"Vittal, A., Marek-Sadowska, M.: Minimal delay interconnect design using alphabetic trees. In: Proceedings of the 31st Annual Design Automation Conference, pp. 392\u2013396. ACM (1994)","DOI":"10.1145\/196244.196432"},{"key":"149_CR36","doi-asserted-by":"crossref","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":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0149-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0149-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0149-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0149-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:47:24Z","timestamp":1559072844000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0149-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,27]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,5]]}},"alternative-id":["149"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0149-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,4,27]]}}}