{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T08:48:54Z","timestamp":1774687734520,"version":"3.50.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,5,24]],"date-time":"2023-05-24T00:00:00Z","timestamp":1684886400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,24]],"date-time":"2023-05-24T00:00:00Z","timestamp":1684886400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"eutsche forschungsgemeinschaft","award":["BU\u00a02313\/6"],"award-info":[{"award-number":["BU\u00a02313\/6"]}]},{"DOI":"10.13039\/501100001659","name":"deutsche forschungsgemeinschaft","doi-asserted-by":"crossref","award":["EXC\u00a059 and EXC-2047 (Hausdorff Center for Mathematics)"],"award-info":[{"award-number":["EXC\u00a059 and EXC-2047 (Hausdorff Center for Mathematics)"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"deutsche forschungsgemeinschaft","doi-asserted-by":"crossref","award":["EXC\u00a059 and EXC-2047 (Hausdorff Center for Mathematics)"],"award-info":[{"award-number":["EXC\u00a059 and EXC-2047 (Hausdorff Center for Mathematics)"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"deutsche forschungsgemeinschaft","doi-asserted-by":"crossref","award":["EXC\u00a059 and EXC-2047 (Hausdorff Center for Mathematics)"],"award-info":[{"award-number":["EXC\u00a059 and EXC-2047 (Hausdorff Center for Mathematics)"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We develop new algorithmic techniques for VLSI detailed routing. First, we improve the goal-oriented version of Dijkstra\u2019s algorithm to find shortest paths in huge incomplete grid graphs with edge costs depending on the direction and the layer, and possibly on rectangular regions. We devise estimates of the distance to the targets that offer better trade-offs between running time and quality than previously known methods, leading to an overall speed-up. Second, we combine the advantages of the two classical detailed routing approaches\u2014global shortest path search and track assignment with local corrections\u2014by treating input wires (such as the output of track assignment) as reservations that can be used at a discount by the respective net. We show how to implement this new approach efficiently.\n<\/jats:p>","DOI":"10.1007\/s10107-023-01962-4","type":"journal-article","created":{"date-parts":[[2023,5,24]],"date-time":"2023-05-24T10:02:41Z","timestamp":1684922561000},"page":"3-32","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Faster goal-oriented shortest path search for bulk and incremental detailed routing"],"prefix":"10.1007","volume":"206","author":[{"given":"Markus","family":"Ahrens","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9190-642X","authenticated-orcid":false,"given":"Dorothee","family":"Henke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9204-3010","authenticated-orcid":false,"given":"Stefan","family":"Rabenstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens","family":"Vygen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,24]]},"reference":[{"key":"1962_CR1","unstructured":"Ahrens, M.: Efficient algorithms for routing a net subject to VLSI design rules. Ph.D. thesis, University of Bonn (2020)"},{"key":"1962_CR2","doi-asserted-by":"crossref","unstructured":"Ahrens, M., Gester, M., Klewinghaus, N., M\u00fcller, D., Peyer, S., Schulte, C., T\u00e9llez, G.: Detailed routing algorithms for advanced technology nodes. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 34(4), 563\u2013576 (2015)","DOI":"10.1109\/TCAD.2014.2385755"},{"key":"1962_CR3","doi-asserted-by":"crossref","unstructured":"Alpert, C.J., Mehta, D.P., Sapatnekar, S.S.: Handbook of Algorithms for Physical Design Automation. CRC Press (2008)","DOI":"10.1201\/9781420013481"},{"key":"1962_CR4","doi-asserted-by":"crossref","unstructured":"Batterywala, S., Shenoy, N., Nicholls, W., Zhou, H.: Track assignment: a desirable intermediate step between global routing and detailed routing. In: Proceedings of the 2002 IEEE\/ACM International Conference on Computer-Aided Design , pp.\u00a059\u201366 (2002)","DOI":"10.1145\/774572.774581"},{"issue":"1","key":"1962_CR5","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269\u2013271 (1959)","journal-title":"Numer. Math."},{"issue":"2","key":"1962_CR6","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Guibas, L., Stolfi, J.: Optimal point location in a monotone subdivision. SIAM J. Comput. 15(2), 317\u2013340 (1986)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1962_CR7","doi-asserted-by":"publisher","first-page":"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(2), 1\u201324 (2013)","journal-title":"ACM Trans. Des. Autom. Electron. Syst."},{"key":"1962_CR8","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"P Hart","year":"1968","unstructured":"Hart, P., Nilsson, N., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4, 100\u2013107 (1968)","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"issue":"2","key":"1962_CR9","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1109\/TCAD.2017.2697964","volume":"37","author":"S Held","year":"2018","unstructured":"Held, S., M\u00fcller, D., Rotter, D., Scheifele, R., Traub, V., Vygen, J.: Global routing with timing constraints. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 37(2), 406\u2013419 (2018)","journal-title":"IEEE Trans. Comput. Aided Des. Integr. Circuits Syst."},{"key":"1962_CR10","unstructured":"Hetzel, A.: A sequential detailed router for huge grid graphs. In: Proceedings of Design, Automation and Test in Europe. IEEE, pp.\u00a0332\u2013338 (1998)"},{"issue":"1","key":"1962_CR11","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D.: Optimal search in planar subdivisions. SIAM J. Comput. 12(1), 28\u201335 (1983)","journal-title":"SIAM J. Comput."},{"key":"1962_CR12","unstructured":"Klewinghaus, N.: Efficient Detailed Routing on Optimized Tracks. Ph.D. thesis, University of Bonn (2022)"},{"key":"1962_CR13","unstructured":"Lawler, E., Luby, M., Parker, B.: Finding shortest paths in very large networks. In: Nagl, M., Perl, J., Linz, T. (Eds), Proceedings of Graph-Theoretic Concepts in Computer Science (1983)"},{"key":"1962_CR14","doi-asserted-by":"crossref","unstructured":"Lipton, H.J., Tarjan, R.E.: Applications of a planar separator theorem. In: 18th Annual IEEE Symposium on Foundations of Computer Science, pp. 162\u2013170 (1977)","DOI":"10.1109\/SFCS.1977.6"},{"issue":"1","key":"1962_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s12532-011-0023-y","volume":"3","author":"D M\u00fcller","year":"2011","unstructured":"M\u00fcller, D., Radke, K., Vygen, J.: Faster min-max resource sharing in theory and practice. Math. Program. Comput. 3(1), 1\u201335 (2011)","journal-title":"Math. Program. Comput."},{"issue":"4","key":"1962_CR16","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1016\/j.jda.2007.08.003","volume":"7","author":"S Peyer","year":"2009","unstructured":"Peyer, S., Rautenbach, D., Vygen, J.: A generalization of Dijkstra\u2019s shortest path algorithm with applications to VLSI routing. J. Discrete Algorithms 7(4), 377\u2013390 (2009)","journal-title":"J. Discrete Algorithms"},{"issue":"1","key":"1962_CR17","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0304-3975(79)90055-0","volume":"8","author":"FP Preparata","year":"1979","unstructured":"Preparata, F.P., M\u00fcller, D.E.: Finding the intersection of n half-spaces in time $$O(n \\log n)$$. Theoret. Comput. Sci. 8(1), 45\u201355 (1979)","journal-title":"Theoret. Comput. Sci."},{"key":"1962_CR18","doi-asserted-by":"publisher","first-page":"907","DOI":"10.1109\/T-C.1974.224054","volume":"23","author":"F Rubin","year":"1974","unstructured":"Rubin, F.: The Lee path connection algorithm. IEEE Trans. Comput. 23, 907\u2013914 (1974)","journal-title":"IEEE Trans. Comput."},{"issue":"7","key":"1962_CR19","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N Sarnak","year":"1986","unstructured":"Sarnak, N., Tarjan, R.: Planar point location using persistent search trees. Commun. ACM 29(7), 669\u2013679 (1986)","journal-title":"Commun. ACM"},{"issue":"1","key":"1962_CR20","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1142\/S0218195994000057","volume":"4","author":"M Sarrafzadeh","year":"1994","unstructured":"Sarrafzadeh, M., Lee, D.-T.: Restricted track assignment with applications. Int. J. Comput. Geom. Appl. 4(1), 53\u201368 (1994)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"1962_CR21","doi-asserted-by":"crossref","unstructured":"T\u00e9llez, G., Hu, J., Wei, Y.: Routing. In: Lavagno, L., Markov, I.L., Martin, G., Scheffer, L.K. (Eds), Electronic Design Automation for IC Implementation, Circuit Design, and Process Technology. CRC Press (2016)","DOI":"10.1201\/b19714-10"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01962-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-01962-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01962-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,24]],"date-time":"2024-07-24T12:20:13Z","timestamp":1721823613000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-01962-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,24]]},"references-count":21,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["1962"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-01962-4","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,24]]},"assertion":[{"value":"11 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 May 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}