{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:59Z","timestamp":1725663779035},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540571551"},{"type":"electronic","value":"9783540479185"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57155-8_266","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:06:30Z","timestamp":1330257990000},"page":"409-420","source":"Crossref","is-referenced-by-count":1,"title":["Improved parallel depth-first search in undirected planar graphs"],"prefix":"10.1007","author":[{"given":"Ming-Yang","family":"Kao","sequence":"first","affiliation":[]},{"given":"Shang-Hua","family":"Teng","sequence":"additional","affiliation":[]},{"given":"Kentaro","family":"Toyama","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"38_CR1","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0196-6774(89)90017-5","volume":"10","author":"K. Abrahamson","year":"1989","unstructured":"K. Abrahamson, N. Dadoun, D. G. Kirkpatrick, and T. Przytycka, A simple tree contraction algorithm, Journal of Algorithms, 10 (1989), pp. 287\u2013302.","journal-title":"Journal of Algorithms"},{"key":"38_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02122548","volume":"8","author":"A. Aggarwal","year":"1988","unstructured":"A. Aggarwal and R. J. Anderson, A random NC algorithm for depth first search, Combinatorica, 8 (1988), pp. 1\u201312.","journal-title":"Combinatorica"},{"key":"38_CR3","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1137\/0219025","volume":"19","author":"A. Aggarwal","year":"1990","unstructured":"A. Aggarwal, R. J. Anderson, and M. Y. Kao, Parallel depth-first search in general directed graphs, SIAM J. Comput., 19 (1990), pp. 397\u2013409.","journal-title":"SIAM J. Comput."},{"key":"38_CR4","unstructured":"A. V. Aho, J. E. Hopcropt, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974."},{"key":"38_CR5","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1007\/BF01759076","volume":"6","author":"R. J. Anderson","year":"1991","unstructured":"R. J. Anderson and G. L. Miller, Deterministic parallel list ranking, Algorithmica, 6 (1991), pp. 859\u2013868.","journal-title":"Algorithmica"},{"key":"38_CR6","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1016\/0022-0000(84)90003-5","volume":"29","author":"M. Atallah","year":"1984","unstructured":"M. Atallah and U. Vishkin, Finding euler tours in parallel, Journal of Computer and System Sciences, 29 (1984), pp. 330\u2013337.","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR7","volume-title":"Graphs","author":"C. Berge","year":"1985","unstructured":"C. Berge, Graphs, North-Holland, New York, second revised ed., 1985.","edition":"second revised"},{"key":"38_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-9967-7","volume-title":"Graph Theory","author":"B. Bollob\u00e1s","year":"1979","unstructured":"B. Bollob\u00e1s, Graph Theory, Springer-Verlag, New York, 1979."},{"key":"38_CR9","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/BF01762121","volume":"3","author":"R. Cole","year":"1988","unstructured":"R. Cole and U. Vishkin, The accelerated centroid decomposition technique for optimal tree evaluation in logarithmic time, Algorithmica, 3 (1988), pp. 329\u2013346.","journal-title":"Algorithmica"},{"key":"38_CR10","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1016\/0890-5401(89)90036-9","volume":"81","author":"R. Cole","year":"1989","unstructured":"R. Cole and U. Vishkin, Faster optimal prefix sums and list ranking, Information and Computation, 81 (1989), pp. 334\u2013352.","journal-title":"Information and Computation"},{"key":"38_CR11","volume-title":"Introduction to Algorithms","author":"T. H. Cormen","year":"1991","unstructured":"T. H. Cormen, C. L. Leiserson, and R. L. Rivest, Introduction to Algorithms, The MIT Press, Cambridge, Massachusetts, 1991."},{"key":"38_CR12","first-page":"646","volume":"7","author":"J. Edmonds","year":"1960","unstructured":"J. Edmonds, A combinatorial representation for polyhedral surfaces, American Mathematical Society Notices, 7 (1960), p. 646.","journal-title":"American Mathematical Society Notices"},{"key":"38_CR13","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/978-1-4684-5511-3_9","volume-title":"Concurrent Computations: Algorithms, Architecture, and Technology","author":"H. Gazit","year":"1988","unstructured":"H. Gazit, G. L. Miller, and S. H. Teng, Optimal tree contraction in the EREW model, in Concurrent Computations: Algorithms, Architecture, and Technology, S. T. Dickinson and B.W. Dickinson and S. Schwartz, eds., Plenum, New York, 1988, pp. 139\u2013156."},{"key":"38_CR14","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/0890-5401(89)90027-8","volume":"81","author":"A. M. Gibbons","year":"1989","unstructured":"A. M. Gibbons and W. Rytter, An optimal parallel algorithm for dynamic expression evaluation and its applications, Information and Computation, 81 (1989), pp. 32\u201345.","journal-title":"Information and Computation"},{"key":"38_CR15","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0890-5401(90)90034-F","volume":"84","author":"T. Hagerup","year":"1990","unstructured":"T. Hagerup, Optimal parallel algorithms on planar graphs, Information and Computation, 84 (1990), pp. 71\u201396.","journal-title":"Information and Computation"},{"key":"38_CR16","doi-asserted-by":"crossref","first-page":"678","DOI":"10.1137\/0219047","volume":"19","author":"T. Hagerup","year":"1990","unstructured":"T. Hagerup, Planar depth-first search in O(log n) parallel time, SIAM J. Comput., 19 (1990), pp. 678\u2013704.","journal-title":"SIAM J. Comput."},{"key":"38_CR17","doi-asserted-by":"crossref","first-page":"1149","DOI":"10.1109\/12.93747","volume":"40","author":"Y. Han","year":"1991","unstructured":"Y. Han, An optimal linked list prefix algorithm on a local memory computer, IEEE Transactions on Computers, 40 (1991), pp. 1149\u20131153.","journal-title":"IEEE Transactions on Computers"},{"key":"38_CR18","doi-asserted-by":"crossref","unstructured":"F. Harary, Graph Theory, Addison-Wesley, 1969.","DOI":"10.21236\/AD0705364"},{"key":"38_CR19","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1016\/0196-6774(91)90012-N","volume":"12","author":"X. He","year":"1991","unstructured":"X. He, Efficient parallel algorithms for series parallel graphs, Journal of Algorithms, 12 (1991), pp. 409\u2013430.","journal-title":"Journal of Algorithms"},{"key":"38_CR20","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1137\/0217028","volume":"17","author":"X. He","year":"1988","unstructured":"X. He and Y. Yesha, A nearly optimal parallel algorithm for constructing depth first spanning trees in planar graphs, SIAM J. Comput., 17 (1988), pp. 486\u2013491.","journal-title":"SIAM J. Comput."},{"key":"38_CR21","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1109\/31.1743","volume":"35","author":"J. Ja'Ja","year":"1988","unstructured":"J. Ja'Ja and S. Kosaraju, Parallel algorithms for planar graphs and related problems, IEEE Trans. Circuits and Systems, 35 (1988), pp. 304\u2013311.","journal-title":"IEEE Trans. Circuits and Systems"},{"key":"38_CR22","doi-asserted-by":"crossref","unstructured":"M. Y. Kao, All graphs have cycle separators and planar directed depth-first search is in DNC, in Lecture Notes in Computer Science 319: the 3rd Aegean Workshop on Computing, Springer-Verlag, 1988, pp. 53\u201363.","DOI":"10.1007\/BFb0040373"},{"key":"38_CR23","unstructured":"-, Planar strong connectivity helps in parallel depth-first search, in Proceedings of the 1992 International Computer Symposium, 1992, pp. 309\u2013316."},{"key":"38_CR24","doi-asserted-by":"crossref","unstructured":"M. Y. Kao and P. N. Klein, Towards overcoming ike transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs, in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990, pp. 181\u2013192.","DOI":"10.1145\/100216.100237"},{"key":"38_CR25","doi-asserted-by":"crossref","unstructured":"R. Karp and V. Ramachandran, A survey of parallel algorithms for shared-memory machines, in Handbook of Theoretical Computer Science: Algorithms and Complexity, J. van Leeuwen, ed., vol. A, Elsevier Science Publishers B. V., 1990, pp. 869\u2013941.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"38_CR26","doi-asserted-by":"crossref","unstructured":"P. N. Klein, Efficient parallel algorithms for chordal graphs, in Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, 1988, pp. 150\u2013161.","DOI":"10.1109\/SFCS.1988.21933"},{"key":"38_CR27","doi-asserted-by":"crossref","unstructured":"S. R. Kosaraju and A. L. Delcher, Optimal parallel evaluation of tree-structured computations by raking, in Lecture Notes in Computer Science 319: the 3rd Aegean Workshop on Computing, Springer-Verlag, 1988, pp. 101\u2013110.","DOI":"10.1007\/BFb0040378"},{"key":"38_CR28","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1109\/TC.1985.6312202","volume":"C-34","author":"C. P. Kruskal","year":"1985","unstructured":"C. P. Kruskal, L. Rudolph, and M. Snir, The power of parallel prefix, IEEE Transactions on Computers, C-34 (1985), pp. 965\u2013968.","journal-title":"IEEE Transactions on Computers"},{"key":"38_CR29","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, Parallel prefix computation, Journal of the ACM, 27 (1980), pp. 831\u2013838.","journal-title":"Journal of the ACM"},{"key":"38_CR30","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0022-0000(86)90030-9","volume":"32","author":"G. L. Miller","year":"1986","unstructured":"G. L. Miller, Finding small simple cycle separators for 2-connected planar graphs, Journal of Computer and System Sciences, 32 (1986), pp. 265\u2013279.","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR31","first-page":"47","volume-title":"Advances in Computing Research: Randomness and Computation","author":"G. L. Miller","year":"1989","unstructured":"G. L. Miller and J. H. Reif, Parallel tree contraction, part 1: Fundamentals, in Advances in Computing Research: Randomness and Computation, S. Micali, ed., vol. 5, JAI Press, Greenwich, CT, 1989, pp. 47\u201372."},{"key":"38_CR32","doi-asserted-by":"crossref","unstructured":"V. Ramachandran and J. H. Reif, An optimal parallel algorithm for graph planarity, in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 282\u2013287.","DOI":"10.1109\/SFCS.1989.63491"},{"key":"38_CR33","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0190(85)90024-9","volume":"20","author":"J. H. Reif","year":"1985","unstructured":"J. H. Reif, Depth-first search is inherently sequential, Information Processing Letters, 20 (1985), pp. 229\u2013234.","journal-title":"Information Processing Letters"},{"key":"38_CR34","doi-asserted-by":"crossref","first-page":"814","DOI":"10.1137\/0215058","volume":"15","author":"J. R. Smith","year":"1986","unstructured":"J. R. Smith, Parallel algorithms for depth-first search I. Planar graphs, SIAM J. Comput., 15 (1986), pp. 814\u2013830.","journal-title":"SIAM J. Comput."},{"key":"38_CR35","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R. Tarjan","year":"1972","unstructured":"R. Tarjan, Depth-first search and linear graph algorithms, SIAM J. Coinput., 1 (1972), pp. 146\u2013160.","journal-title":"SIAM J. Coinput."},{"key":"38_CR36","unstructured":"W. Tutte, Graph Theory, vol. 21 of Encyclopedia of Mathematics and its Applications, Addison-Wesley, 1984."},{"key":"38_CR37","unstructured":"A. T. White, Graphs, Groups, and Surfaces, North-Holland, 1973."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57155-8_266.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:08:21Z","timestamp":1605647301000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57155-8_266"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540571551","9783540479185"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/3-540-57155-8_266","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}