{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:40:24Z","timestamp":1742596824770,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540575689"},{"type":"electronic","value":"9783540482338"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57568-5_277","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:10:44Z","timestamp":1330261844000},"page":"456-465","source":"Crossref","is-referenced-by-count":0,"title":["Parallel algorithms for single-layer channel routing"],"prefix":"10.1007","author":[{"given":"Ronald I.","family":"Greenberg","sequence":"first","affiliation":[]},{"given":"Shih-Chuan","family":"Hung","sequence":"additional","affiliation":[]},{"given":"Jau-Der","family":"Shih","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"49_CR1","doi-asserted-by":"crossref","unstructured":"Alok Aggarwal and James Park. Notes on searching in multidimensional monotone arrays. In 29th Annual Symposium on Foundations of Computer Science, pages 497\u2013512. IEEE Computer Society Press, 1988.","DOI":"10.1109\/SFCS.1988.21966"},{"key":"49_CR2","unstructured":"O. Berkman, Baruch Schieber, and U. Vishkin. Some doubly logarithmic optimal parallel algorithms based on finding all nearest smaller values. Technical Report UMIACS-TR-88-79, University of Maryland Institute for Advanced Computer Studies, October 1988. To appear in J. Algorithms."},{"key":"49_CR3","doi-asserted-by":"crossref","unstructured":"O. Berkman and U. Vishkin. Recursive star-tree parallel data-structure. Technical Report UMIACS-TR-90-40, University of Maryland Institute for Advanced Computer Studies, March 1990.","DOI":"10.21236\/ADA227803"},{"key":"49_CR4","unstructured":"Shing-Chong Chang, Joseph J\u00e1J\u00e1, and Kwan Woo Ryu. Optimal parallel algorithms for one-layer routing. Technical Report UMIACS-TR-89-46, University of Maryland Institute for Advanced Computer Studies, April 1989."},{"key":"49_CR5","first-page":"334","volume":"81","author":"R. Cole","year":"1989","unstructured":"R. Cole and U. Vishkin. Faster optimal prefix sums and list ranking. Information and Control, 81:334\u2013352, 1989.","journal-title":"Information and Control"},{"key":"49_CR6","unstructured":"Danny Dolev, Kevin Karplus, Alan Siegel, Alex Strong, and Jeffrey D. Ullman. Optimal algorithms for structural assembly. VLSI Design, pages 38\u201343, 1982. Earlier version in Proceedings of the 13th ACM Symposium on Theory of Computing."},{"issue":"4","key":"49_CR7","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0020-0190(92)90201-6","volume":"43","author":"R. I. Greenberg","year":"1992","unstructured":"Ronald I. Greenberg and F. Miller Maley. Minimum separation for single-layer channel routing. Information Processing Letters, 43(4):201\u2013205, September 1992.","journal-title":"Information Processing Letters"},{"key":"49_CR8","doi-asserted-by":"crossref","unstructured":"Ronald I. Greenberg and Jau-Der Shih. Feasible offset and optimal offset for single-layer channel routing. In Proceedings of 2nd Annual Israel Symposium on Theory of Computing and Systems, pages 193\u2013201. IEEE Computer Society Press, June 1993. Revised version submitted to SIAM Journal on Discrete Mathematics.","DOI":"10.1109\/ISTCS.1993.253470"},{"key":"49_CR9","unstructured":"Ronald I. Greenberg and Jau-Der Shih. Single-layer channel routing and placement with single-sided nets. Submitted to Discrete Applied Mathematics, 1993."},{"key":"49_CR10","doi-asserted-by":"crossref","unstructured":"Torben Hagerup. Constant-time parallel integer sorting. In Proceedings of the 23rd ACM Symposium on Theory of Computing, pages 299\u2013306. ACM Press, 1991.","DOI":"10.1145\/103418.103452"},{"key":"49_CR11","unstructured":"Joseph J\u00e1J\u00e1. An Introduction to Parallel Algorithms. Addison-Wesley, 1992."},{"issue":"10","key":"49_CR12","doi-asserted-by":"crossref","first-page":"942","DOI":"10.1109\/TC.1983.1676138","volume":"C-32","author":"D. Kruskal","year":"1983","unstructured":"D. Kruskal. Searching, merging and sorting in parallel computation. IEEE Trans. Computers, C-32(10):942\u2013946, October 1983.","journal-title":"IEEE Trans. Computers"},{"issue":"4","key":"49_CR13","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1145\/322217.322232","volume":"27","author":"R. E. Ladner","year":"1980","unstructured":"R. E. Ladner and M. J. Fischer. Parallel prefix computation. Journal of the ACM, 27(4):831\u2013838, October 1980.","journal-title":"Journal of the ACM"},{"key":"49_CR14","unstructured":"F. Miller Maley. Single-Layer Wire Routing and Compaction. MIT Press, 1990."},{"key":"49_CR15","doi-asserted-by":"crossref","unstructured":"Yossi Matias and Uzi Vishkin. Converting high probability into nearly-constant time \u2014 with applications to parallel hashing. In Proceedings of the 23rd ACM Symposium on Theory of Computing, pages 307\u2013316. ACM Press, 1991.","DOI":"10.1145\/103418.103453"},{"key":"49_CR16","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/0022-0000(87)90004-3","volume":"34","author":"A. Mirzaian","year":"1987","unstructured":"Andranik Mirzaian. River routing in VLSI. Journal of Computer and System Sciences, 34:43\u201354, 1987.","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57568-5_277.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:11:32Z","timestamp":1742595092000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57568-5_277"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540575689","9783540482338"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-57568-5_277","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}