{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T11:51:51Z","timestamp":1759146711070},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"1-6","license":[{"start":{"date-parts":[[1991,6,1]],"date-time":"1991-06-01T00:00:00Z","timestamp":675734400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1991,6]]},"DOI":"10.1007\/bf01759035","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T10:43:56Z","timestamp":1118918636000},"page":"73-82","source":"Crossref","is-referenced-by-count":31,"title":["Multiterminal global routing: A deterministic approximation scheme"],"prefix":"10.1007","volume":"6","author":[{"given":"Prabhakar","family":"Raghavan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Clark D.","family":"Thompson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"no. 1","key":"BF01759035_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0166-218X(81)90022-6","volume":"3","author":"J. Beck","year":"1981","unstructured":"J. Beck and T. Fiala, \u201cInteger-Making\u201d Theorems,Discrete Applied Mathematics, vol. 3, no. 1, pp. 1\u20138, February 1981.","journal-title":"Discrete Applied Mathematics"},{"issue":"no. 4","key":"BF01759035_CR2","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1109\/TCAD.1983.1270040","volume":"2","author":"M. Burstein","year":"1983","unstructured":"M. Burstein and R. Pelavin, Hierarchical Wire Routing,IEEE Transactions on Computer-Aided Design, vol. 2, no. 4, pp. 223\u2013234, October 1983.","journal-title":"IEEE Transactions on Computer-Aided Design"},{"issue":"no. 4","key":"BF01759035_CR3","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N. Karmarkar","year":"1984","unstructured":"N. Karmarkar, A New Polynomial-Time Algorithm for Linear Programming,Combinatorica, vol. 4, no. 4, pp. 373\u2013396, 1984.","journal-title":"Combinatorica"},{"key":"BF01759035_CR4","doi-asserted-by":"crossref","unstructured":"R. M. Karp, F. T. Leighton, C. D. Thompson, R. I. Rivest, U. V. Vazirani, and V. V. Vazirani, Global Wire Routing in Two-Dimensional Arrays,Proceedings of the 24th Annual IEEE Symposium on FOCS, pp. 453\u2013459, October 1983. Also submitted toAlgorithmica.","DOI":"10.1109\/SFCS.1983.23"},{"issue":"no. 4","key":"BF01759035_CR5","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1109\/TCAD.1983.1270039","volume":"2","author":"S. Kirkpatrick","year":"1983","unstructured":"S. Kirkpatrick and M. P. Vecchi, Global Wiring by Simulated Annealing,IEEE Transactions on Computer-Aided Design, vol. 2, no. 4, pp. 215\u2013222, October 1983.","journal-title":"IEEE Transactions on Computer-Aided Design"},{"key":"BF01759035_CR6","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1109\/TEC.1961.5219222","volume":"10","author":"C. Y. Lee","year":"1961","unstructured":"C. Y. Lee, An Algorithm for Path Connections and Its Applications,IRE Transactions on Electronic Computers, vol. 10, pp. 346\u2013365, September 1961.","journal-title":"IRE Transactions on Electronic Computers"},{"key":"BF01759035_CR7","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0020-0190(78)90016-9","volume":"7","author":"V. M. Malhotra","year":"1978","unstructured":"V. M. Malhotra, M. P. Kumar, and S. N. Maheshwari, AnO(\u00a6V\u00a63) Algorithm for Finding Maximum Flows in Networks,Information Processing Letters, vol. 7, pp. 277\u2013278, 1978.","journal-title":"Information Processing Letters"},{"issue":"no. 3","key":"BF01759035_CR8","first-page":"229","volume":"6","author":"A. P.-C. Ng","year":"1987","unstructured":"A. P.-C. Ng, P. Raghavan, and C. D. Thompson, Experimental Results with a Linear Program Global Router,Computers and Artificial Intelligence, vol. 6, no. 3, pp. 229\u2013242, 1987.","journal-title":"Computers and Artificial Intelligence"},{"issue":"no. 1","key":"BF01759035_CR9","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0097-3165(78)90028-6","volume":"25","author":"J. E. Olson","year":"1978","unstructured":"J. E. Olson and J. Spencer, Balancing Families of Sets,Journal of Combinatorial Theory, Series A, vol. 25, no. 1, pp. 29\u201337, July 1978.","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"BF01759035_CR10","series-title":"Technical Report UCB\/CSD\/87\/ 312","volume-title":"Ph.D. Thesis","author":"P. Raghavan","year":"1986","unstructured":"P. Raghavan, Randomized Rounding and Discrete Ham-Sandwich Theorems: Provably Good Algorithms for Routing and Packing Problems, Ph.D. Thesis, Technical Report UCB\/CSD\/87\/ 312, University of California, Berkeley, October 1986."},{"key":"BF01759035_CR11","doi-asserted-by":"crossref","unstructured":"P. Raghavan, Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs,Proceedings of the 27th Annual IEEE Symposium on FOCS, October 1986.","DOI":"10.1109\/SFCS.1986.45"},{"key":"BF01759035_CR12","doi-asserted-by":"crossref","unstructured":"P. Raghavan and C. D. Thompson, Provably Good Routing in Graphs: Regular Arrays,Proceedings of the 24th ACM STOC, pp. 79\u201387, May 1985.","DOI":"10.1145\/22145.22154"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01759035.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01759035\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01759035","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T19:27:04Z","timestamp":1586287624000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01759035"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,6]]},"references-count":12,"journal-issue":{"issue":"1-6","published-print":{"date-parts":[[1991,6]]}},"alternative-id":["BF01759035"],"URL":"https:\/\/doi.org\/10.1007\/bf01759035","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,6]]}}}