{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T13:20:18Z","timestamp":1742390418701},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540507284"},{"type":"electronic","value":"9783540460763"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-50728-0_52","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T15:32:27Z","timestamp":1330183947000},"page":"288-303","source":"Crossref","is-referenced-by-count":4,"title":["A parallel algorithm for channel routing"],"prefix":"10.1007","author":[{"given":"John E.","family":"Savage","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus G.","family":"Wloka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Komlos and E. Szemeredi, \u201cAn O(n log n) Sorting Network,\u201d in 15th Annual ACM Symposium on Theory of Computing, pp. 1\u20139, 1983.","DOI":"10.1145\/800061.808726"},{"key":"21_CR2","first-page":"307","volume":"32","author":"K. E. Batcher","year":"1968","unstructured":"K. E. Batcher and H. S. Stone, \u201cSorting Networks and Their Applications,\u201d AFIPS Proc., Spring Joint Comput. Conf., vol. 32, pp. 307\u2013314, 1968.","journal-title":"AFIPS Proc., Spring Joint Comput. Conf."},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, \u201cLower Bounds for Algebraic Computation Trees,\u201d in 15th Annual ACM Symposium on Theory of Computing, pp. 80\u201386, May 1983.","DOI":"10.1145\/800061.808735"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"R. Cole, \u201cParallel Merge Sort,\u201d in 27th Annual Symposium on Foundations of Computer Science, pp. 511\u2013616, 1986.","DOI":"10.1109\/SFCS.1986.41"},{"key":"21_CR5","unstructured":"B. A. Dalio, \u201cDeCo \u2014 A Hierarchical Device Compilation Systems\u201d Dept. of Computer Science, Brown University, PhD Thesis CS-87-08, May 1987."},{"key":"21_CR6","unstructured":"B. A. Dalio and J. E. Savage, \u201cDeCo \u2014 A Device Compilation System,\u201d in International Workshop on Logic and Architecture Synthesis for Silicon Compilers, May 1988."},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"D. N. Deutsch, \u201cA Dogleg Channel Router,\u201d in Proc. 13th IEEE Design Automation Conf., pp. 425\u2013433, 1976.","DOI":"10.1145\/800146.804843"},{"key":"21_CR8","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0022-0000(79)90054-0","volume":"18","author":"D. Dobkin","year":"1979","unstructured":"D. Dobkin and R. Lipton, \u201cOn the Complexity of Computations under Varying Set of Primitives,\u201d Journal of Computer and Systems Sciences, vol. 18, pp. 86\u201391, 1979.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"21_CR9","doi-asserted-by":"crossref","unstructured":"D. Dolev, K. Karplus, A. Siegel, A. Strong and J. D. Ullman, \u201cOptimal Wiring between Rectangles,\u201d in 13th Annual ACM Symposium on Theory of Computing, pp. 312\u2013317, 1981.","DOI":"10.1145\/800076.802484"},{"key":"21_CR10","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. Golumbic","year":"1980","unstructured":"M. Golumbic, Algorithmic Graph Theory and Perfect Graphs. New York, NY, Academic Press, 1980."},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"A. Hashimoto and J. Stevens, \u201cWire Routing by Optimizing Channel Assignments within Large Apertures,\u201d in Proc. 6th IEEE Design Automation Conf., pp. 155\u2013163, 1971.","DOI":"10.1145\/800158.805069"},{"key":"21_CR12","volume-title":"CMOS3 Cell Library","author":"D. V. Heinbuch","year":"1988","unstructured":"D. V. Heinbuch, CMOS3 Cell Library. Reading, MA, Addison Wesley, 1988."},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"D. Helmbold and E. Mayr, \u201cApplications of Parallel Scheduling to Perfect Graphs,\u201d Stanford University,, 1986.","DOI":"10.1007\/3-540-17218-1_59"},{"key":"21_CR14","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1145\/359138.359141","volume":"22","author":"D. S. Hirschberg","year":"1979","unstructured":"D. S. Hirschberg, A. K. Chandra and D. V. Sarvate, \u201cComputing Connected Components on a Computer,\u201d CACM, vol. 22, pp. 461\u2013464, 1979.","journal-title":"CACM"},{"key":"21_CR15","unstructured":"R. M. Karp and V. Ramachandran, \u201cA Survey of Parallel Algorithms for Shared-Memory Machines,\u201d in Handbook of Theoretical Computer Science. North-Holland, 1988, preprint."},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"P. N. Klein, \u201cEfficient Parallel Algorithms for Chordal Graphs,\u201d in 29th Annual Symposium on Foundations of Computer Science, to appear, 1988.","DOI":"10.1109\/SFCS.1988.21933"},{"issue":"1","key":"21_CR17","first-page":"25","volume":"CAD-1","author":"E. S. Kuh","year":"1982","unstructured":"E. S. Kuh and T. Yoshimura, \u201cEfficient Algorithms for Channel Routing,\u201d IEEE Trans. Computer-Aided Design, vol. CAD-1, no. 1, pp. 25\u201335, Jan. 1982.","journal-title":"IEEE Trans. Computer-Aided Design"},{"key":"21_CR18","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1145\/322217.322232","volume":"27","author":"R. E. Ladner","year":"1980","unstructured":"R. E. Ladner and M. J. Fischer, \u201cParallel Prefix Computation,\u201d JACM, vol. 27, pp. 831\u2013838, 1980.","journal-title":"JACM"},{"key":"21_CR19","volume-title":"Algorithms for Integrated Circuit Layout: an Analytic Approach","author":"A. S. Lapaugh","year":"1980","unstructured":"A. S. Lapaugh, \u201cAlgorithms for Integrated Circuit Layout: an Analytic Approach,\u201d Dept. of Electrical Engineering and Computer Science, M.I.T., PhD Thesis, 1980."},{"key":"21_CR20","volume-title":"Advanced Parallel and VLSI Computation","author":"T. Leighton","year":"1988","unstructured":"T. Leighton, C. E. Leiserson, B. Maggs, S. Plotkin and J. Wein, \u201cAdvanced Parallel and VLSI Computation,\u201d Dept. of Electrical Engineering and Computer Science, M.I.T., MIT\/LCS\/RSS 2, Mar. 1988."},{"key":"21_CR21","unstructured":"T. Leighton, C. E. Leiserson, B. Maggs, S. Plotkin and J. Wein, \u201cTheory of Parallel and VLSI Computation,\u201d Dept. of Electrical Engineering and Computer Science, M.I.T., MIT\/LCS\/RSS 1, Mar. 1988."},{"key":"21_CR22","doi-asserted-by":"crossref","unstructured":"T. Leighton, \u201cTight Bounds on the Complexity of Parallel Sorting,\u201d in 16th Annual ACM Symposium on Theory of Computing, pp. 71\u201380, 1984.","DOI":"10.1145\/800057.808667"},{"key":"21_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos, Computational Geometry. Springer-Verlag New York Inc., 1985."},{"issue":"3","key":"21_CR24","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1109\/TCAD.1985.1270117","volume":"CAD-4","author":"J. Reed","year":"1985","unstructured":"J. Reed, A. Sangiovanni-Vincentelli and M. Santomauro, \u201cA New Symbolic Channel Router: YACR2,\u201d IEEE Trans. Computer-Aided Design, vol. CAD-4, no. 3, pp. 208\u2013219, July 1985.","journal-title":"IEEE Trans. Computer-Aided Design"},{"key":"21_CR25","unstructured":"S. P. Reiss and J. E. Savage, \u201cSLAP \u2014 A Methodology for Silicon Layout,\u201d in Procs. Intl. Conf. on Circuits and Computers, pp. 281\u2013285, 1982."},{"key":"21_CR26","doi-asserted-by":"crossref","unstructured":"R. L. Rivest and C. M. Fiduccia, \u201cA \u201eGreedy\u201d Channel Router,\u201d in Proc. 19th IEEE Design Automation Conf., pp. 418\u2013424, 1982.","DOI":"10.1109\/DAC.1982.1585533"},{"issue":"4","key":"21_CR27","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1109\/TCAD.1987.1270298","volume":"CAD-6","author":"M. Sarrafzadeh","year":"1987","unstructured":"M. Sarrafzadeh, \u201cChannel-Routing Problem in the Knock-Knee Mode is NP-Complete,\u201d IEEE Trans. Computer-Aided Design, vol. CAD-6, no. 4, pp. 503\u2013506, July 1987.","journal-title":"IEEE Trans. Computer-Aided Design"},{"key":"21_CR28","first-page":"637","volume-title":"IEEE Intl. Conf. On Computer Design","author":"J. E. Savage","year":"1983","unstructured":"J. E. Savage, \u201cHeuristics in the SLAP Layout System,\u201d in IEEE Intl. Conf. On Computer Design, Rye, New York, pp. 637\u2013640, 1983."},{"key":"21_CR29","unstructured":"J. E. Savage, \u201cThree VLSI Compilation Techniques: PLA's, Weinberger Arrays, and SLAP, A New Silicon Layout Program,\u201d in Algorithmically-Specialized Computers. Academic Press, 1983."},{"key":"21_CR30","unstructured":"J. E. Savage, \u201cHeuristics for Level Graph Embeddings,\u201d in 9th Intl. Workshop on Graphtheoretic Concepts in Computer Science, pp. 307\u2013318, June 1983."},{"issue":"1","key":"21_CR31","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1109\/TCAD.1985.1270096","volume":"CAD-4","author":"T. G. Szymanski","year":"1985","unstructured":"T. G. Szymanski, \u201cDogleg Channel Routing is NP-Complete,\u201d IEEE Trans. Computer-Aided Design, vol. CAD-4, no. 1, pp. 31\u201340, Jan. 1985.","journal-title":"IEEE Trans. Computer-Aided Design"},{"key":"21_CR32","doi-asserted-by":"crossref","unstructured":"M. R. Zargham, \u201cParallel Channel Routing,\u201d in Proc. 25th IEEE Design Automation Conf., pp. 128\u2013133, 1988.","DOI":"10.1109\/DAC.1988.14747"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-50728-0_52.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:18:48Z","timestamp":1605629928000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-50728-0_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540507284","9783540460763"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/3-540-50728-0_52","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}