{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:03:06Z","timestamp":1725663786998},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540571551"},{"type":"electronic","value":"9783540479185"}],"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":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57155-8_282","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T07:07:04Z","timestamp":1330240024000},"page":"589-600","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast algorithms for one-dimensionsal compaction with jog insertion"],"prefix":"10.1007","author":[{"given":"Matthias F. M.","family":"Stallmann","sequence":"first","affiliation":[]},{"given":"Thomas A.","family":"Hughes","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"54_CR1","unstructured":"Heather D. Booth. Some Fast Algorithms on Graphs and Trees. PhD thesis, Princeton University, 1991."},{"key":"54_CR2","volume-title":"Part II: Finger searching. Technical Report 471","author":"R. Cole","year":"1989","unstructured":"R. Cole. On the dynamic finger conjecture for aplay trees. Part II: Finger searching. Technical Report 471, Courant Institute, Dept. of Computer Science, 251 Mercer St., New York, N.Y. 10012, October 1989."},{"key":"54_CR3","unstructured":"T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, 1990."},{"key":"54_CR4","unstructured":"D.N. Deutsch. Compacted channel routing. In International Conference on Computer-Aided Design, Digest of Technical Papers, pages 223\u2013225, 1985."},{"key":"54_CR5","unstructured":"J.-M. Ho, M. Sarrafzadeh, and A. Suzuki. An exact algorithm for single-layer wire-length minimization. In International Conference on Computer-Aided Design, Digest of Technical Papers, pages 424\u2013427, 1990."},{"key":"54_CR6","volume-title":"PhD thesis","author":"T. A. Hughes","year":"1992","unstructured":"Thomas A. Hughes. Topological Routing Problems. PhD thesis, North Carolina State University, Dept. of Electrical and Computer Engineering, Raleigh, NC 27695-7911, 1992."},{"key":"54_CR7","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, 5:408\u2013421, 1984.","journal-title":"Journal of Algorithms"},{"key":"54_CR8","unstructured":"M. Lorenzetti, M. Nifong, and J. Rose. Channel routing for compaction. In Proc. MCNC International Workshop on Placement and Routing, May 1988."},{"key":"54_CR9","doi-asserted-by":"crossref","unstructured":"F.M. Maley. Compaction with automatic jog introduction. In Chapel Hill Conference on VLSI, pages 261\u2013283, 1985.","DOI":"10.21236\/ADA176525"},{"key":"54_CR10","unstructured":"F.M. Maley. Single-Layer Wire Routing. PhD thesis, Massachusetts Institute of Technology, 1987."},{"issue":"2","key":"54_CR11","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1109\/43.46782","volume":"9","author":"K. Mehlhorn","year":"1990","unstructured":"K. Mehlhorn and S. N\u00e4her. A faster compaction algorithm with automatic jog insertion. IEEE Transactions on Computer-Aided Design of Integrated Circuits, 9(2):158\u2013166, 1990.","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits"},{"key":"54_CR12","unstructured":"Bryan Preas and Michael Lorenzetti, editors. Physical Design Automation of VLSI Systems. Benjamin Cummings, 1988."},{"issue":"3","key":"54_CR13","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D. D. Sleator","year":"1985","unstructured":"D. D. Sleator and R. E. Tarjan. Self-adjusting binary search trees. Journal of the ACM, 32(3):652\u2013686, 1985.","journal-title":"Journal of the ACM"},{"issue":"1","key":"54_CR14","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1137\/0217010","volume":"17","author":"R. E. Tarjan","year":"1988","unstructured":"R. E. Tarjan and C. J. Van Wyk. An O(n log log n)-time algorithm for triangulating a simple polygon. SIAM Journal on Computing, 17(1):143\u2013178, 1988.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"54_CR15","first-page":"270","volume":"10","author":"T. C. Tuan","year":"1991","unstructured":"T. C. Tuan and K. H. Teo. On river routing with minimum number of jogs. IEEE Transactions on Computer-Aided Design of Integrated Circuits, 10(2):270\u2013273, 1991.","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits"},{"key":"54_CR16","unstructured":"L.P.P.P. van Ginneken and J.A.G. Jess. Gridless routing of general floor plans. In IC-CAD, pages 30\u201333, 1987."},{"key":"54_CR17","doi-asserted-by":"crossref","unstructured":"X.-M. Xiong and E. Kuh. Nutcracker: An efficient and intelligent channel spacer. In Z4th Design Automation Conference, pages 298\u2013304, 1987.","DOI":"10.1145\/37888.37933"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57155-8_282","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T08:45:25Z","timestamp":1558255525000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57155-8_282"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540571551","9783540479185"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-57155-8_282","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]},"assertion":[{"value":"9 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}