{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,26]],"date-time":"2025-12-26T17:36:59Z","timestamp":1766770619877,"version":"3.48.0"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,12,26]],"date-time":"2025-12-26T00:00:00Z","timestamp":1766707200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,12,26]],"date-time":"2025-12-26T00:00:00Z","timestamp":1766707200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62202192"],"award-info":[{"award-number":["62202192"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Interdiciplinary Research Program of Hust","award":["2025JCYJ021"],"award-info":[{"award-number":["2025JCYJ021"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"DOI":"10.1007\/s11227-025-08139-0","type":"journal-article","created":{"date-parts":[[2025,12,26]],"date-time":"2025-12-26T17:33:35Z","timestamp":1766770415000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An edge replacement heuristic algorithm for length-restricted Steiner minimum tree problem"],"prefix":"10.1007","volume":"82","author":[{"given":"Tiancheng","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhipeng","family":"L\u00fc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junwen","family":"Ding","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,12,26]]},"reference":[{"issue":"4","key":"8139_CR1","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey MR, Johnson DS (1977) The rectilinear Steiner tree problem is NP-complete. J SIAM Appl Math 32(4):826\u2013834","journal-title":"J SIAM Appl Math"},{"issue":"2","key":"8139_CR2","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/0114025","volume":"14","author":"M Hanan","year":"1966","unstructured":"Hanan M (1966) On Steiner\u2019s problem with rectilinear distance. SIAM J Appl Math 14(2):255\u2013265","journal-title":"SIAM J Appl Math"},{"key":"8139_CR3","doi-asserted-by":"crossref","unstructured":"Warme DM, Winter P, Zachariasen M (2000) Exact algorithms for plane Steiner tree problems: a computational study. Adv Steiner Trees, 81\u2013116","DOI":"10.1007\/978-1-4757-3171-2_6"},{"issue":"12","key":"8139_CR4","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1109\/43.331412","volume":"13","author":"M Borah","year":"1994","unstructured":"Borah M, Owens RM, Irwin MJ (1994) An edge-based heuristic for Steiner routing. IEEE Transact Comput-Aided Design Integr Circuits Syst 13(12):1563\u20131568","journal-title":"IEEE Transact Comput-Aided Design Integr Circuits Syst"},{"key":"8139_CR5","doi-asserted-by":"crossref","unstructured":"Zhou H (2003) Efficient Steiner tree construction based on spanning graphs. In: Proceedings of the 2003 International Symposium on Physical Design, 152\u2013157. Association for Computing Machinery, New York, NY, USA","DOI":"10.1145\/640000.640034"},{"key":"8139_CR6","doi-asserted-by":"crossref","unstructured":"Zhou H, Shenoy N, Nicholls W (2001) Efficient minimum spanning tree construction without Delaunay triangulation. In: Proceedings of the 2001 Asia and South Pacific Design Automation Conference, 192\u2013197. Association for Computing Machinery, New York, NY, USA","DOI":"10.1145\/370155.370320"},{"key":"8139_CR7","doi-asserted-by":"crossref","unstructured":"Kahng AB, M\u0103ndoiu II, Zelikovsky AZ (2003) Highly scalable algorithms for rectilinear and octilinear Steiner trees. In: Proceedings of the 2003 Asia and South Pacific Design Automation Conference, 827\u2013833. Association for Computing Machinery, New York, NY, USA","DOI":"10.1145\/1119772.1119955"},{"issue":"11","key":"8139_CR8","doi-asserted-by":"publisher","first-page":"2083","DOI":"10.1109\/TCAD.2008.2006085","volume":"27","author":"S Cinel","year":"2008","unstructured":"Cinel S, Bazlamacci CF (2008) A distributed heuristic algorithm for the rectilinear Steiner minimal tree problem. IEEE Trans Comput Aided Des Integr Circuits Syst 27(11):2083\u20132087","journal-title":"IEEE Trans Comput Aided Des Integr Circuits Syst"},{"issue":"1","key":"8139_CR9","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 (2008) FLUTE: Fast lookup table based rectilinear Steiner minimal tree algorithm for VLSI design. IEEE Trans Comput Aided Des Integr Circuits Syst 27(1):70\u201383","journal-title":"IEEE Trans Comput Aided Des Integr Circuits Syst"},{"key":"8139_CR10","doi-asserted-by":"crossref","unstructured":"Vani V, Prasad GR (2016) Augmented line segment based algorithm for constructing rectilinear steiner minimum tree. In: 2016 International Conference on Communication and Electronics Systems, 1\u20135","DOI":"10.1109\/CESYS.2016.7889854"},{"issue":"1","key":"8139_CR11","doi-asserted-by":"publisher","first-page":"46","DOI":"10.4018\/IJECME.2020010104","volume":"9","author":"NR Latha","year":"2020","unstructured":"Latha NR, Prasad GR (2020) Memory and I\/O optimized rectilinear Steiner minimum tree routing for VLSI. Int J Electron Commun Meas Eng 9(1):46\u201359","journal-title":"Int J Electron Commun Meas Eng"},{"key":"8139_CR12","doi-asserted-by":"crossref","unstructured":"Ganley JL, Cohoon JP (1994) Routing a multi-terminal critical net: Steiner tree construction in the presence of obstacles. In: Proceedings of IEEE International Symposium on Circuits and Systems - ISCAS \u201994, 1, 113\u2013116","DOI":"10.1109\/ISCAS.1994.408768"},{"key":"8139_CR13","doi-asserted-by":"crossref","unstructured":"Li L, Qian Z, Young EFY (2009) Generation of optimal obstacle-avoiding rectilinear Steiner minimum tree. In: 2009 IEEE\/ACM International Conference on Computer-Aided Design - Digest of Technical Papers, 1, 21\u201325","DOI":"10.1145\/1687399.1687405"},{"key":"8139_CR14","doi-asserted-by":"crossref","unstructured":"Huang T, Young EFY (2010) Obstacle-avoiding rectilinear Steiner minimum tree construction: An optimal approach. In: 2010 IEEE\/ACM International Conference on Computer-Aided Design, 610\u2013613","DOI":"10.1109\/ICCAD.2010.5654220"},{"issue":"6","key":"8139_CR15","doi-asserted-by":"publisher","first-page":"882","DOI":"10.1109\/TCAD.2013.2238291","volume":"32","author":"T Huang","year":"2013","unstructured":"Huang T, Young EFY (2013) ObSteiner: an exact algorithm for the construction of rectilinear Steiner minimum trees in the presence of complex rectilinear obstacles. IEEE Trans Comput Aided Des Integr Circuits Syst 32(6):882\u2013893","journal-title":"IEEE Trans Comput Aided Des Integr Circuits Syst"},{"issue":"4","key":"8139_CR16","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1109\/TCAD.2008.917583","volume":"27","author":"C-W Lin","year":"2008","unstructured":"Lin C-W, Chen S-Y, Li C-F, Chang Y-W, Yang C-L (2008) Obstacle-avoiding rectilinear Steiner tree construction based on spanning graphs. IEEE Trans Comput Aided Des Integr Circuits Syst 27(4):643\u2013653","journal-title":"IEEE Trans Comput Aided Des Integr Circuits Syst"},{"issue":"2","key":"8139_CR17","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1109\/TCAD.2010.2096571","volume":"30","author":"G Ajwani","year":"2011","unstructured":"Ajwani G, Chu C, Mak W-K (2011) FOARS: FLUTE Based Obstacle-Avoiding Rectilinear Steiner Tree Construction. IEEE Trans Comput Aided Des Integr Circuits Syst 30(2):194\u2013204","journal-title":"IEEE Trans Comput Aided Des Integr Circuits Syst"},{"issue":"1","key":"8139_CR18","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.vlsi.2013.08.001","volume":"47","author":"W-K Chow","year":"2014","unstructured":"Chow W-K, Li L, Young EFY, Sham C-W (2014) Obstacle-avoiding rectilinear Steiner tree construction in sequential and parallel approach. Integration 47(1):105\u2013114","journal-title":"Integration"},{"issue":"4","key":"8139_CR19","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1007\/s00521-014-1760-4","volume":"26","author":"H Zhang","year":"2015","unstructured":"Zhang H, Ye DY (2015) Key-node-based local search discrete artificial bee colony algorithm for obstacle-avoiding rectilinear Steiner tree construction. Neural Comput Appl 26(4):875\u2013898","journal-title":"Neural Comput Appl"},{"key":"8139_CR20","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1016\/j.apm.2019.10.027","volume":"78","author":"W Guo","year":"2020","unstructured":"Guo W, Huang X (2020) PORA: a Physarum-inspired obstacle-avoiding routing algorithm for integrated circuit design. Appl Math Model 78:268\u2013286","journal-title":"Appl Math Model"},{"issue":"6","key":"8139_CR21","first-page":"1","volume":"69","author":"S Kundu","year":"2021","unstructured":"Kundu S, Roy S, Mukherjee S (2021) An efficient obstacle-avoiding rectilinear Steiner tree construction method using PB-SAT. IETE J Res 69(6):1\u201311","journal-title":"IETE J Res"},{"issue":"1","key":"8139_CR22","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1109\/TETCI.2023.3306241","volume":"8","author":"T Zhang","year":"2024","unstructured":"Zhang T, L\u00fc Z, Ding J (2024) Guiding solution based local search for obstacle-avoiding rectilinear Steiner minimal tree problem. IEEE Transact Emerg Top Comput Intell 8(1):440\u2013453","journal-title":"IEEE Transact Emerg Top Comput Intell"},{"key":"8139_CR23","doi-asserted-by":"crossref","unstructured":"Guo J, Kong H, Feng L (2024) A rule-based high efficient obstacle-avoiding RSMT algorithm for VLSI routing. In: 2024 IEEE International Symposium on Circuits and Systems, 1\u20135","DOI":"10.1109\/ISCAS58744.2024.10558430"},{"key":"8139_CR24","doi-asserted-by":"crossref","unstructured":"Zhang Y, Chakraborty A, Chowdhury S, Pan DZ (2012) Reclaiming over-the-IP-block routing resources with buffering-aware rectilinear Steiner minimum tree construction. In: Proceedings of the International Conference on Computer-Aided Design, 137\u2013143","DOI":"10.1145\/2429384.2429410"},{"key":"8139_CR25","doi-asserted-by":"crossref","unstructured":"Huang T, Young EFY (2012) Construction of rectilinear Steiner minimum trees with slew constraints over obstacles. In: Proceedings of the International Conference on Computer-Aided Design, 144\u2013151","DOI":"10.1145\/2429384.2429411"},{"key":"8139_CR26","doi-asserted-by":"crossref","unstructured":"Zhang Y, Pan DZ (2014) Timing-driven, over-the-block rectilinear Steiner tree construction with pre-buffering and slew constraints. In: Proceedings of the 2014 on International Symposium on Physical Design, 29\u201336","DOI":"10.1145\/2560519.2560533"},{"key":"8139_CR27","doi-asserted-by":"crossref","unstructured":"Shyamala G, Prasad GR (2017) Obstacle aware delay optimized rectilinear Steiner minimum tree routing. In: 2017 2nd IEEE International Conference on Recent Trends in Electronics, Information & Communication Technology, 2194\u20132197","DOI":"10.1109\/RTEICT.2017.8256989"},{"issue":"4","key":"8139_CR28","first-page":"1","volume":"13","author":"G Liu","year":"2022","unstructured":"Liu G, Zhu Y, Xu S, Tang H, Chen Y-C (2022) Performance-driven X-architecture routing algorithm for artificial intelligence chip design in smart manufacturing. ACM Trans Manag Inf Syst 13(4):1\u201320","journal-title":"ACM Trans Manag Inf Syst"},{"key":"8139_CR29","doi-asserted-by":"crossref","unstructured":"M\u00fcller-Hannemann M, Peyer S (2003) Approximation of rectilinear Steiner trees with length restrictions on obstacles. In: Algorithms and Data Structures, 207\u2013218","DOI":"10.1007\/978-3-540-45078-8_19"},{"key":"8139_CR30","doi-asserted-by":"crossref","unstructured":"Held S, Spirkl ST (2014) A fast algorithm for rectilinear steiner trees with length restrictions on obstacles. In: Proceedings of the 2014 on International Symposium on Physical Design, 37\u201344","DOI":"10.1145\/2560519.2560529"},{"key":"8139_CR31","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1016\/j.vlsi.2016.06.001","volume":"55","author":"H Zhang","year":"2016","unstructured":"Zhang H, Ye D, Guo W (2016) A heuristic for constructing a rectilinear Steiner tree by reusing routing resources over obstacles. Integration 55:162\u2013175","journal-title":"Integration"},{"key":"8139_CR32","unstructured":"Delaunay B (1934) Sur la sph\u00e8re vide. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk 7, 793\u2013800"},{"issue":"6","key":"8139_CR33","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"RC Prim","year":"1957","unstructured":"Prim RC (1957) Shortest connection networks and some generalizations. Bell Syst Tech J 36(6):1389\u20131401","journal-title":"Bell Syst Tech J"},{"issue":"2","key":"8139_CR34","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"PE Hart","year":"1968","unstructured":"Hart PE, Nilsson NJ, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Transact Syst Sci Cybernet 4(2):100\u2013107","journal-title":"IEEE Transact Syst Sci Cybernet"},{"issue":"3","key":"8139_CR35","first-page":"1","volume":"21","author":"X Huang","year":"2016","unstructured":"Huang X, Guo W, Liu G, Chen G (2016) FH-OAOS: a fast four-step heuristic for obstacle-avoiding octilinear Steiner tree construction. ACM Transact Des Autom Electron Syste 21(3):1\u201331","journal-title":"ACM Transact Des Autom Electron Syste"},{"key":"8139_CR36","doi-asserted-by":"crossref","unstructured":"Feng Z, Hu Y, Jing T, Hong X, Hu X, Yan G (2006) An $$O(n \\log n)$$ algorithm for obstacle-avoiding routing tree construction in the $$\\lambda$$-geometry plane. In: Proceedings of the 2006 International Symposium on Physical Design, 1, 48\u201355. Association for Computing Machinery, New York, NY, USA","DOI":"10.1145\/1123008.1123020"},{"key":"8139_CR37","doi-asserted-by":"crossref","unstructured":"Long J, Zhou H, Memik SO (2008) An $$O(n \\log n)$$ Edge-Based Algorithm for Obstacle-Avoiding Rectilinear Steiner Tree Construction. In: Proceedings of the 2008 International Symposium on Physical Design, pp. 126\u2013133. Association for Computing Machinery, New York, NY, USA","DOI":"10.1145\/1353629.1353658"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-025-08139-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-025-08139-0","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-025-08139-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,26]],"date-time":"2025-12-26T17:33:38Z","timestamp":1766770418000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-025-08139-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,26]]},"references-count":37,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,1]]}},"alternative-id":["8139"],"URL":"https:\/\/doi.org\/10.1007\/s11227-025-08139-0","relation":{},"ISSN":["1573-0484"],"issn-type":[{"value":"1573-0484","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,26]]},"assertion":[{"value":"7 August 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 December 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 December 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"34"}}