{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T19:40:20Z","timestamp":1735760420486,"version":"3.32.0"},"reference-count":27,"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\/bf01759037","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T10:43:56Z","timestamp":1118918636000},"page":"103-128","source":"Crossref","is-referenced-by-count":4,"title":["A generic algorithm for one-dimensional homotopic compaction"],"prefix":"10.1007","volume":"6","author":[{"given":"F.","family":"Miller Maley","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"R. Cole and A. Siegel, River routing every which way, but loose,Proceedings of the 25th Annual Symposium on Foundations of Computer Science (October 1984), pp. 65\u201373.","key":"BF01759037_CR1","DOI":"10.1109\/SFCS.1984.715902"},{"issue":"No. 5","key":"BF01759037_CR2","doi-asserted-by":"crossref","first-page":"863","DOI":"10.1109\/TCAD.1987.1270329","volume":"6","author":"J. Doenhardt","year":"1987","unstructured":"J. Doenhardt and T. Lengauer, Algorithmic aspects of one-dimensional layout compaction,IEEE Transactions on Computer-Aided Design, Vol. 6, No. 5 (September 1987), pp. 863\u2013878.","journal-title":"IEEE Transactions on Computer-Aided Design"},{"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,Proceedings of the Fourth Annual Symposium on Computational Geometry (June 1988), pp. 392\u2013402.","key":"BF01759037_CR3","DOI":"10.1145\/73393.73433"},{"doi-asserted-by":"crossref","unstructured":"S. Gao, M. Kaufmann, and F. M. Maley, Advances in homotopic layout compaction,Proceedings of the 1989 ACM Symposium on Parallel Algorithms and Architectures (June 1989), pp. 273\u2013282.","key":"BF01759037_CR4","DOI":"10.1145\/72935.72964"},{"key":"BF01759037_CR5","volume-title":"Ph.D. Thesis","author":"M. Y. Hsueh","year":"1979","unstructured":"M. Y. Hsueh, Symbolic Layout and Compaction of Integrated Circuits, Ph.D. Thesis, EECS Division, University of California, Berkeley, CA (1979)."},{"unstructured":"S. Kaptanoglu, E. Liu, R. Suaya, and J. Valainis, Two dimensional IC-layout compaction based on topological design rule checking, manuscript (1988).","key":"BF01759037_CR6"},{"unstructured":"M. Kaufmann and F. M. Maley, Parity conditions in homotopic knock-knee routing, submitted toAlgorithmica.","key":"BF01759037_CR7"},{"unstructured":"M. Kaufmann and F. M. Maley, Computing congestion during one-dimensional homotopic compaction, submitted toJournal of Algorithms.","key":"BF01759037_CR8"},{"unstructured":"M. Kaufmann and K. Mehlhorn, On Local Routing of Two-Terminal Nets, Technical report, SFB 124, Universit\u00e4t des Saarlandes (1986).","key":"BF01759037_CR9"},{"unstructured":"M. Kaufmann and K. Mehlhorn, A linear-time algorithm for the local routing problem, submitted toSIAM Journal on Computing.","key":"BF01759037_CR10"},{"doi-asserted-by":"crossref","unstructured":"G. Kedem and H. Watanabe, Graph-optimization techniques for IC layout and compaction,Proceedings of the 20th Design Automation Conference (June 1983), pp. 113\u2013120.","key":"BF01759037_CR11","DOI":"10.1109\/DAC.1983.1585635"},{"doi-asserted-by":"crossref","unstructured":"C. E. Leiserson and F. M. Maley, Algorithms for routing and testing routability of planar VLSI layouts,Proceedings of the 17th Annual ACM Symposium on Theory of Computing (May 1985), pp. 69\u201378.","key":"BF01759037_CR12","DOI":"10.1145\/22145.22153"},{"unstructured":"C. E. Leiserson and J. B. Saxe, A mixed-integer linear programming problem which is efficiently solvable,Proceedings of the 21st Annual Allerton Conference on Communication, Control, and Computing (October 1983), pp. 204\u2013213.","key":"BF01759037_CR13"},{"issue":"No. 3","key":"BF01759037_CR14","doi-asserted-by":"crossref","first-page":"408","DOI":"10.1016\/0196-6774(84)90020-8","volume":"5","author":"T. Lengauer","year":"1984","unstructured":"T. Lengauer, On the solution of inequality systems relevant to IC layout,Journal of Algorithms, Vol. 5, No. 3 (September 1984), pp. 408\u2013421.","journal-title":"Journal of Algorithms"},{"issue":"No. 2","key":"BF01759037_CR15","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1109\/TCAD.1983.1270022","volume":"2","author":"Y.-Z. Liao","year":"1983","unstructured":"Y.-Z. Liao and C. K. Wong, An algorithm to compact a VLSI symbolic layout with mixed constraints,IEEE Transactions on Computer-Aided Design, Vol. 2, No. 2 (1983), pp. 62\u201369.","journal-title":"IEEE Transactions on Computer-Aided Design"},{"doi-asserted-by":"crossref","unstructured":"F. M. Maley, Compaction with automatic jog introduction,Proceedings of the 1985 Chapel Hill Conference on VLSI (May 1985), pp. 261\u2013283.","key":"BF01759037_CR16","DOI":"10.21236\/ADA176525"},{"doi-asserted-by":"crossref","unstructured":"F. M. Maley, Compaction with Automatic Jog Introduction, M. S. Thesis, MIT EECS Department (November 1986); available as MIT\/LCS\/TR-372.","key":"BF01759037_CR17","DOI":"10.21236\/ADA176525"},{"issue":"No. 2","key":"BF01759037_CR18","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0020-0190(87)90230-4","volume":"25","author":"F. M. Maley","year":"1987","unstructured":"F. M. Maley, An observation concerning constraint-based compaction,Information Processing Letters, Vol. 25, No. 2 (May 1987), pp. 119\u2013122.","journal-title":"Information Processing Letters"},{"doi-asserted-by":"crossref","unstructured":"F. M. Maley, Toward a mathematical theory of single-layer wire routing,Proceedings of the Fifth MIT Conference on Advanced Research in VLSI (March 1988), pp. 277\u2013296.","key":"BF01759037_CR19","DOI":"10.7551\/mitpress\/1102.003.0023"},{"key":"BF01759037_CR20","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, Massachusetts (1989)."},{"unstructured":"F. M. Maley, Mathematical properties of the sketch model of VLSI layout, in preparation; see instead [20].","key":"BF01759037_CR21"},{"doi-asserted-by":"crossref","unstructured":"K. Mehlhorn and S. N\u00e4her, A faster compaction algorithm with automatic jog insertion,Proceedings of the Fifth MIT Conference on Advanced Research in VLSI (March 1988), pp. 297\u2013314.","key":"BF01759037_CR22","DOI":"10.7551\/mitpress\/1102.003.0024"},{"unstructured":"R. C. Mosteller, A. H. Frey, and R. Suaya, 2-D compaction, a Monte Carlo method,Advanced Research on VLSI: 1987 Stanford Conference (April 1987), pp. 173\u2013197.","key":"BF01759037_CR23"},{"key":"BF01759037_CR24","volume-title":"Elements of Algebraic Topology","author":"J. R. Munkres","year":"1984","unstructured":"J. R. Munkres,Elements of Algebraic Topology, Benjamin\/Cummings, Reading, Massachusetts (1984)."},{"unstructured":"R. Y. Pinter, The Impact of Layer Assignment Methods on Layout Algorithms for Integrated Circuits, Ph.D. Thesis, MIT EECS Department (1982); available as MIT\/LCS\/TR-291.","key":"BF01759037_CR25"},{"doi-asserted-by":"crossref","unstructured":"W. S. Scott and J. K. Ousterhout, Plowing: interactive stretching and compaction in Magic,Proceedings of the 21st Design Automation Conference (June 1984), pp. 166\u2013172.","key":"BF01759037_CR26","DOI":"10.1109\/DAC.1984.1585791"},{"unstructured":"W. Wolf, An experimental comparison of 1-D compaction algorithms,Proceedings of the 1985 Chapel Hill Conference on VLSI (May 1985), pp. 165\u2013179.","key":"BF01759037_CR27"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01759037.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01759037\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01759037","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T19:05:27Z","timestamp":1735758327000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01759037"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,6]]},"references-count":27,"journal-issue":{"issue":"1-6","published-print":{"date-parts":[[1991,6]]}},"alternative-id":["BF01759037"],"URL":"https:\/\/doi.org\/10.1007\/bf01759037","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[1991,6]]}}}