{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,24]],"date-time":"2024-12-24T05:11:40Z","timestamp":1735017100725,"version":"3.32.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1993,1,1]],"date-time":"1993-01-01T00:00:00Z","timestamp":725846400000},"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":[[1993,1]]},"DOI":"10.1007\/bf01185338","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T16:45:05Z","timestamp":1108745105000},"page":"47-63","source":"Crossref","is-referenced-by-count":2,"title":["Parity conditions in homotopic knock-knee routing"],"prefix":"10.1007","volume":"9","author":[{"given":"Michael","family":"Kaufmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F. Miller","family":"Maley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"No. 2","key":"CR1","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/BF00289496","volume":"23","author":"M. Becker","year":"1986","unstructured":"M. Becker and K. Mehlhorn, Algorithms for routing in planar graphs,Ada Informatica, Vol. 23, No. 2 (1986), pp. 163?176.","journal-title":"Ada Informatica"},{"key":"CR2","unstructured":"M. L. Brady and D. J. Brown, Arbitrary planar routing with four layers,1984 Conference on Advanced Research in VLSI, MIT (January 1984), pp. 194?201."},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"R. Cole and A. Siegel, River routing every which way, but loose,25th Annual Symposium on Foundations of Computer Science (October 1984), pp. 65?73.","DOI":"10.1109\/SFCS.1984.715902"},{"issue":"No. 4","key":"CR4","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/BF02579432","volume":"2","author":"A. Frank","year":"1982","unstructured":"A. Frank, Disjoint paths in a rectilinear grid,Combinatorica, Vol. 2, No. 4 (1982), pp. 361?371.","journal-title":"Combinatorica"},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"S. Gao, M. Jerrum, M. Kaufmann, K. Mehlhorn, W. R\u00fclling, and C. Storb, On continuous homotopic one layer routing,Fourth Annual Symposium on Computational Geometry (June 1988), pp. 392?402.","DOI":"10.1145\/73393.73433"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"S. Gao, M. Kaufmann, and F. M. Maley, Advances in homotopic layout compaction,1989 ACM Symposium on Parallel Algorithms and Architectures (June 1989), pp. 273?282.","DOI":"10.1145\/72935.72964"},{"key":"CR7","unstructured":"M. Kaufmann and K. Mehlhorn, On local routing of two-terminal nets, Technical Report, SFB 124, Universit\u00e4t des Saarlandes (1986); submitted toJournal of Combinatorial Theory Series B."},{"issue":"No. 4","key":"CR8","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1016\/0196-6774(86)90016-7","volume":"7","author":"M. Kaufmann","year":"1986","unstructured":"M. Kaufmann and K. Mehlhorn, Routing through a generalized switchbox,Journal of Algorithms, Vol. 7, No. 4 (1986), pp. 510?531.","journal-title":"Journal of Algorithms"},{"key":"CR9","unstructured":"M. Kaufmann and K. Mehlhorn, A linear-time algorithm for the local routing problem, submitted toSIAM Journal on Computing."},{"key":"CR10","volume-title":"Technical Report RUU-CS-82-4","author":"M. R. Kramer","year":"1982","unstructured":"M. R. Kramer and J. van Leeuwen, Wire-routing is NP-complete, Technical Report RUU-CS-82-4, Department of Computer Science, University of Utrecht, the Netherlands (February 1982)."},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"C. E. Leiserson and F. M. Maley, Algorithms for routing and testing routability of planar VLSI layouts,17th Annual ACM Symposium on Theory of Computing (May 1985), pp. 69?78.","DOI":"10.1145\/22145.22153"},{"key":"CR12","first-page":"231","volume-title":"Advances in Computing Research, Vol. 2","author":"W. Lipski Jr.","year":"1984","unstructured":"W. Lipski, Jr., On the structure of three-layer wirable layouts, inAdvances in Computing Research, Vol. 2 (edited by F. P. Preparata), JAI Press, Greenwich, CT, 1984, pp. 231?243."},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"F. M. Maley, Compaction with automatic jog introduction,1985 Chapel Hill Conference on VLSI (May 1985), pp. 261?283.","DOI":"10.21236\/ADA176525"},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"F. M. Maley, Toward a mathematical theory of single-layer wire routing,Fifth MIT Conference on Advanced Research in VLSI (March 1988), pp. 277?296.","DOI":"10.7551\/mitpress\/1102.003.0023"},{"key":"CR15","volume-title":"Single-Layer Wire Routing and Compaction","author":"F. M. Maley","year":"1989","unstructured":"F. M. Maley,Single-Layer Wire Routing and Compaction, MIT Press, Cambridge, MA (1989)."},{"key":"CR16","unstructured":"F. M. Maley, A generic algorithm for one-dimensional homotopic compaction,Algorithmica, to appear."},{"issue":"No. 2","key":"CR17","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1137\/0215034","volume":"15","author":"K. Matsumoto","year":"1986","unstructured":"K. Matsumoto, T. Nishizeki, and N. Saito, An efficient algorithm for finding multi-commodity flows in planar networks,SIAM Journal on Computing, Vol. 15, No. 2 (1986), pp. 495?510.","journal-title":"SIAM Journal on Computing"},{"issue":"No. 1","key":"CR18","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,Journal of the ACM, Vol. 33, No. 1 (1986), pp. 60?85.","journal-title":"Journal of the ACM"},{"issue":"No. 1","key":"CR19","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1109\/TCAD.1985.1270099","volume":"CAD-4","author":"T. Nishizeki","year":"1985","unstructured":"T. Nishizeki, N. Saito, and K. Suzuki, A linear-time routing algorithm for convex grids,IEEE Transactions on Computer-Aided Design, Vol. CAD-4, No. 1 (1985), pp. 68?76.","journal-title":"IEEE Transactions on Computer-Aided Design"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0095-8956(81)80012-3","volume":"31","author":"H. Okamura","year":"1981","unstructured":"H. Okamura and P. Seymour, Multicommodity flows in planar graphs,Journal of Combinatorial Theory Series B, Vol. 31 (1981), pp. 75?81.","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1109\/TC.1984.1676459","volume":"C-33","author":"F. P. Preparata","year":"1984","unstructured":"F. P. Preparata and W. Lipski, Jr., Optimal three-layer channel routing,IEEE Transactions on Computers, Vol. C-33 (1984), pp. 350?357.","journal-title":"IEEE Transactions on Computers"},{"key":"CR22","unstructured":"A. Schrijver, Decomposition of graphs on surfaces and a homotopic circulation theorem, preprint."},{"key":"CR23","unstructured":"A. Schrijver, Edge-disjoint homotopic paths in straight-line planar graphs, preprint."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01185338.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01185338\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01185338","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T12:55:35Z","timestamp":1734958535000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01185338"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,1]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1993,1]]}},"alternative-id":["BF01185338"],"URL":"https:\/\/doi.org\/10.1007\/bf01185338","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[1993,1]]}}}