{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T05:24:11Z","timestamp":1648531451341},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540638902","type":"print"},{"value":"9783540696629","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63890-3_34","type":"book-chapter","created":{"date-parts":[[2010,4,5]],"date-time":"2010-04-05T17:12:11Z","timestamp":1270487531000},"page":"314-323","source":"Crossref","is-referenced-by-count":0,"title":["Algorithms for finding optimal disjoint paths around a rectangle"],"prefix":"10.1007","author":[{"given":"Wun-Tat","family":"Chan","sequence":"first","affiliation":[]},{"given":"Francis Y. L.","family":"Chin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,7,29]]},"reference":[{"key":"34_CR1","volume-title":"Network Flow: Theory, Algorithms and Applications","author":"R. K. Ahuja","year":"1993","unstructured":"R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flow: Theory, Algorithms and Applications, Prentice Hall, Englewood Cliffs, NJ, 1993."},{"key":"34_CR2","unstructured":"W.-T. Chan and F. Y. L. Chin, Efficient algorithms for finding disjoint paths in grids (extended abstract), in Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997, pp. 454\u2013463."},{"key":"34_CR3","unstructured":"W.-T. Chan and F. Y. L. Chin, Linear-time algorithms for unspecified routing in grids, in ICS'96-International Conference on Algorithms, 1996, pp. 79\u201385."},{"key":"34_CR4","first-page":"47","volume-title":"Paths, Flows, and VLSI-Layout","author":"A. Frank","year":"1990","unstructured":"A. Frank, Packing paths, circuits, and cuts \u2014 a survey, Paths, Flows, and VLSI-Layout, Springer-Verlag, Berlin, (1990), pp. 47\u2013100."},{"key":"34_CR5","first-page":"363","volume":"40","author":"A. Frank","year":"1992","unstructured":"A. Frank, T. Nishizeki, N. Saito, H. Suzuki, and E. Tardos, Algorithms for routing around a rectangle, DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science, 40 (1992), pp. 363\u2013378.","journal-title":"DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science"},{"key":"34_CR6","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1145\/48014.48018","volume":"35","author":"T. F. Gonzalez","year":"1988","unstructured":"T. F. Gonzalez and S.-L. Lee, A linear time algorithm for optimal routing around a rectangle, J. ACM, 35 (1988), pp. 810\u2013831.","journal-title":"J. ACM"},{"key":"34_CR7","doi-asserted-by":"crossref","unstructured":"A. Hashimoto and J. E. Stevens, Wire routing by optimizing channel assignment without large apertures, in Proceedings of the 8th IEEE Design Automation Conference, 1971, pp. 155\u2013169.","DOI":"10.1145\/800158.805069"},{"key":"34_CR8","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/BF01240733","volume":"11","author":"S. Khuller","year":"1994","unstructured":"S. Khuller and J. Naor, Flow in planar graphs with vertex capacities, Algorithmica, 11 (1994), pp. 200\u2013225.","journal-title":"Algorithmica"},{"key":"34_CR9","unstructured":"M. R. Kramer and J. van Leeuwen, The complexity of wire-routing and finding minimum area layouts for arbitrary VLSI circuits, Advances in Computing Research, (1984), pp. 129\u2013146."},{"key":"34_CR10","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1145\/4904.4994","volume":"33","author":"K. Mehlhorn","year":"1986","unstructured":"K. Mehlhorn and F. P. Preparata, Routing through a rectangle, J. ACM, 33 (1986), pp. 60\u201385.","journal-title":"J. ACM"},{"key":"34_CR11","doi-asserted-by":"crossref","unstructured":"G. L. Miller and J. Naor, Flow in planar graphs with multiple sources and sinks (extended abstract), in Proceedings of the 30th IEEE Annual Symposium on Foundations of Computer Science, 1989, pp. 112\u2013117.","DOI":"10.1109\/SFCS.1989.63464"},{"key":"34_CR12","unstructured":"H. Ripphausen-Lipa, D. Wagner, and K. Weihe, Efficient algorithms for disjoint paths in planar graphs, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., (1995), pp. 295\u2013354."},{"key":"34_CR13","unstructured":"H. Ripphausen-Lipa, D. Wagner, and K. Weihe, The vertex-disjoint Menger problem in planar graphs, SIAM J. Comput., (1997), pp. 331\u2013349."},{"key":"34_CR14","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1137\/0603055","volume":"3","author":"F. F. Yao","year":"1982","unstructured":"F. F. Yao, Speed-up in dynamic programming, SIAM J. Alg. Disc. Meth., 3 (1982), pp. 532\u2013540.","journal-title":"SIAM J. Alg. Disc. Meth."}],"container-title":["Algorithms and Computation","Lecture Notes in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63890-3_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T20:38:16Z","timestamp":1558989496000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63890-3_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540638902","9783540696629"],"references-count":14,"URL":"http:\/\/dx.doi.org\/10.1007\/3-540-63890-3_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"published":{"date-parts":[[1997]]}}}