{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:38:23Z","timestamp":1725467903111},"publisher-location":"Berlin\/Heidelberg","reference-count":19,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"0387968180"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0040373","type":"book-chapter","created":{"date-parts":[[2006,8,3]],"date-time":"2006-08-03T00:03:50Z","timestamp":1154563430000},"page":"53-63","source":"Crossref","is-referenced-by-count":10,"title":["All graphs have cycle separators and planar directed depth-first search is in DNC"],"prefix":"10.1007","author":[{"given":"Ming-Yang","family":"Kao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"Alok Aggarwal and Richard J. Anderson. A random NC algorithm for depth first search. In ACM Symposium on Theory of Computing, pages 325\u2013334, 1987.","DOI":"10.1145\/28395.28430"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Alok Aggarwal, Richard J. Anderson, and Ming Y. Kao. Parallel depth-first search in directed graphs. Manuscript, February 1988.","DOI":"10.1145\/73007.73035"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Greg N. Frederickson and Ravi Janardan. Separator-based strategies for efficient message routing. In IEEE Symposium on Foundations of Computer Science, pages 428\u2013437, 1986.","DOI":"10.1109\/SFCS.1986.49"},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/BF01937481","volume":"24","author":"R. K. Ghosh","year":"1984","unstructured":"Ratan K. Ghosh and G. P. Bhattacharjee. A parallel search algorithm for directed acyclic graphs. BIT, 24:134\u2013150, 1984.","journal-title":"BIT"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Hillel Gazit and Gary L. Miller. A parallel algorithm for finding a separator in planar graphs. In IEEE Symposium on Foundations of Computer Science, pages 238\u2013248, 1987.","DOI":"10.1109\/SFCS.1987.3"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Andrew V. Goldberg, Serge A. Plotkin, and Gregory E. Shannon. Parallel symmetry-breaking in sparse graphs. In ACM Symposium on Theory of Computing, pages 315\u2013324, 1987.","DOI":"10.1145\/28395.28429"},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"Donald B. Johnson and Shankar M. Venkatesan. Partition on planar flow networks. In IEEE Symposium on Foundations of Computer Science, pages 259\u2013264, 1983.","DOI":"10.1109\/SFCS.1983.44"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Philip N. Klein and John H. Reif. An efficient parallel algorithm for planarity. In IEEE Symposium on Foundations of Computer Science, pages 465\u2013477, 1986.","DOI":"10.1109\/SFCS.1986.6"},{"issue":"10","key":"6_CR9","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1109\/TC.1985.6312202","volume":"c-34","author":"C. P. Kruskal","year":"1985","unstructured":"Clyde P. Kruskal, Larry Rudolph, and Marc Snir. The power of parallel prefix. IEEE Transactions on Computers, c-34(10):965\u2013968, October 1985.","journal-title":"IEEE Transactions on Computers"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Charles E. Leiserson. Area-efficient graph layouts (for VLSI). In IEEE Symposium on Foundations of Computer Science, pages 270\u2013281, 1980.","DOI":"10.1109\/SFCS.1980.13"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"L. Lov\u00e1sz. Computing ears and branchings. In IEEE Symposium on Foundations of Computer Science, pages 464\u2013467, 1985.","DOI":"10.1109\/SFCS.1985.16"},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"R.J. Lipton","year":"1979","unstructured":"R.J. Lipton, D.J. Rose, and R.E. Tarjan. Generalized nested dissection. SIAM Journal of Numerical Analysis, 16:346\u2013358, 1979.","journal-title":"SIAM Journal of Numerical Analysis"},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"R.J. Lipton and R.E. Tarjan. A separator theorem for planar graphs. SIAM Journal of Applied Mathematics, 36:177\u2013189, 1979.","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Gary L. Miller. Finding small simple cycle separators for 2-connected planar graphs. In ACM Symposium on Theory of Computing, pages 376\u2013382, 1984.","DOI":"10.1145\/800057.808703"},{"key":"6_CR15","unstructured":"Victor Pan and John Reif. Fast and Efficient Solution of Path Algebra Problems. Technical Report 3, Computer Science Department, State University of New York at Albany, 1987."},{"key":"6_CR16","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0020-0190(85)90024-9","volume":"20","author":"J. H. Reif","year":"1985","unstructured":"John H. Reif. Depth-first search is inherently sequential. Information Processing Letters, 20:229\u2013234, June 1985.","journal-title":"Information Processing Letters"},{"issue":"3","key":"6_CR17","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1137\/0215058","volume":"15","author":"J. R. Smith","year":"1986","unstructured":"Justin R. Smith. Parallel algorithms for depth first searchs I. planar graphs. SIAM Journal of Computing, 15(3):814\u2013830, August 1986.","journal-title":"SIAM Journal of Computing"},{"key":"6_CR18","unstructured":"Catherine A. Schevon and Jeffrey Scott Vitter. A Parallel Algorithm for Recognizing Unordered Depth-First Search. Technical Report 21, Department of Computer Science, Brown University, 1985."},{"issue":"2","key":"6_CR19","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1109\/TC.1981.6312176","volume":"30","author":"L.G. Valiant","year":"1981","unstructured":"L.G. Valiant. Universality considerations in 'VLSI circuits. IEEE Transactions on Computers, 30(2):135\u2013140, February 1981.","journal-title":"IEEE Transactions on Computers"}],"container-title":["Lecture Notes in Computer Science","VLSI Algorithms and Architectures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0040373.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:40:11Z","timestamp":1607550011000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0040373"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["0387968180"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/bfb0040373","relation":{},"subject":[]}}