{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T13:56:29Z","timestamp":1778594189429,"version":"3.51.4"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1995,11,1]],"date-time":"1995-11-01T00:00:00Z","timestamp":815184000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1995,11]]},"DOI":"10.1007\/bf01192047","type":"journal-article","created":{"date-parts":[[2005,2,17]],"date-time":"2005-02-17T21:40:03Z","timestamp":1108676403000},"page":"398-408","source":"Crossref","is-referenced-by-count":4,"title":["An optimal parallel algorithm for planar cycle separators"],"prefix":"10.1007","volume":"14","author":[{"given":"Ming-Yang","family":"Kao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shang-Hua","family":"Teng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.","family":"Toyama","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","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:287?302, 1989.","journal-title":"Journal of Algorithms"},{"key":"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 seach,Combinatorica, 8:1?12, 1988.","journal-title":"Combinatorica"},{"key":"CR3","doi-asserted-by":"crossref","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 Journal on Computing, 19:397?409, 1990.","journal-title":"SIAM Journal on Computing"},{"key":"CR4","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"key":"CR5","doi-asserted-by":"crossref","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:859?868, 1991.","journal-title":"Algorithmica"},{"key":"CR6","doi-asserted-by":"crossref","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:330?337, 1984.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR7","volume-title":"Graphs","year":"1985","unstructured":"C. Berge,Graphs, second revised edition, North-Holland, New York, 1985."},{"key":"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":"CR9","doi-asserted-by":"crossref","first-page":"l329","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:l329?346, 1988.","journal-title":"Algorithmica"},{"key":"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:334?352, 1989.","journal-title":"Information and Computation"},{"key":"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, MIT Press, Cambridge, MA, 1991."},{"key":"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:646, 1960.","journal-title":"American Mathematical Society Notices"},{"key":"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 S. K. Tewksbury and B. W. Dickinson and S. C. Schwartz, editors,Concurrent Computations: Algorithms, Architecture, and Technology, Plenum, New York, 1988, pp. 139?156."},{"key":"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:32?45, 1989.","journal-title":"Information and Computation"},{"key":"CR15","doi-asserted-by":"crossref","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:71?96, 1990.","journal-title":"Information and Computation"},{"key":"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(logn) parallel time,SIAM Journal on Computing, 19:678?704, 1990.","journal-title":"SIAM Journal on Computing"},{"key":"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:1149?1153, 1991.","journal-title":"IEEE Transactions on Computers"},{"key":"CR18","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F. Harary","year":"1969","unstructured":"F. Harary,Graph Theory, Addison-Wesley, Reading, MA, 1969."},{"key":"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:409?430, 1991.","journal-title":"Journal of Algorithms"},{"key":"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 Journal on Computing, 17:486?491, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"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 Transactions on Circuits and Systems, 35:304?311, 1988.","journal-title":"IEEE Transactions on Circuits and Systems"},{"key":"CR22","series-title":"VLSI Algorithms and Architectures, the 3rd Aegean Workshop on Computing","first-page":"53","volume-title":"Lecture Notes in Computer Science, volume 319","author":"M. Y. Kao","year":"1988","unstructured":"M. Y. Kao, All graphs have cycle separators and planar directed depth-first search is in DNC. In J. H. Reif, editor, Lecture Notes in Computer Science, volume 319.VLSI Algorithms and Architectures, the 3rd Aegean Workshop on Computing, Springer-Verlag, New York, 1988, pp. 53?63."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1137\/S0097539792227077","volume":"24","author":"M. Y. Kao","year":"1995","unstructured":"M. Y. Kao, Planar strong connectivity helps in parallel depth-first search,SIAM Journal on Computing, 24:46?62, 1995.","journal-title":"SIAM Journal on Computing"},{"key":"CR24","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1016\/0022-0000(93)90042-U","volume":"47","author":"M. Y. Kao","year":"1993","unstructured":"M. Y. Kao and P. N. Klein, Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs,Journal of Computer and System Sciences, 47:459?500, 1993.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR25","first-page":"869","volume-title":"Handbook of Theoretical Computer Science: Algorithms and Complexity, volume A","author":"R. Karp","year":"1990","unstructured":"R. Karp and V. Ramachandran, A survey of parallel algorithms for shared-memory machines. In J. van Leeuwen, editor,Handbook of Theoretical Computer Science: Algorithms and Complexity, volume A, Elsevier, New York, 1990, pp. 869?941."},{"key":"CR26","doi-asserted-by":"crossref","unstructured":"P. N. Klein, Efficient parallel algorithms for chordal graphs,Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, 1988, pp. 150?161.","DOI":"10.1109\/SFCS.1988.21933"},{"key":"CR27","first-page":"101","volume-title":"Lecture Notes in Computer Science, volume 319","author":"S. R. Kosaraju","year":"1988","unstructured":"S. R. Kosaraju and A. L. Delcher, Optimal parallel evaluation of tree-structured computations by raking. In J. H. Reif, editor,VLSI Algorithms and Architectures, the 3rd Aegean Workshop on Computing, Lecture Notes in Computer Science, volume 319, Springer-Verlag, New York, 1988, pp. 101?110."},{"key":"CR28","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1109\/TC.1985.6312202","volume":"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, 34:965?968, 1985.","journal-title":"IEEE Transactions on Computers"},{"key":"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:831?838, 1980.","journal-title":"Journal of the ACM"},{"key":"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:265?279, 1986.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR31","first-page":"47","volume-title":"Advances in Computing Research: Randomness and Computation, volume 5","author":"G. L. Miller","year":"1989","unstructured":"G. L. Miller and J. H. Reif, Parallel tree contraction, part 1: Fundamentals. In S. Micali, editor,Advances in Computing Research: Randomness and Computation, volume 5, JAI Press, Greenwich, CT, 1989, pp. 47?72."},{"key":"CR32","doi-asserted-by":"crossref","first-page":"1128","DOI":"10.1137\/0220070","volume":"20","author":"G. L. Miller","year":"1991","unstructured":"G. L. Miller and J. H. Reif, Parallel tree contraction, part 2: Further applications,SIAM Journal on Computing, 20:1128?1147, 1991.","journal-title":"SIAM Journal on Computing"},{"key":"CR33","doi-asserted-by":"crossref","unstructured":"V. Ramachandran and J. H. Reif, An optimal parallel algorithm for graph planarity,Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 282?287.","DOI":"10.1109\/SFCS.1989.63491"},{"key":"CR34","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:229?234, 1985.","journal-title":"Information Processing Letters"},{"key":"CR35","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0020-0190(88)90048-8","volume":"29","author":"G. E. Shannon","year":"1988","unstructured":"G. E. Shannon, A linear-processor algorithm for depth-first search in planar graphs,Information Processing Letters, 29:119?123, 1988.","journal-title":"Information Processing Letters"},{"key":"CR36","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 Journal on Computing, 15:814?830, 1986.","journal-title":"SIAM Journal on Computing"},{"key":"CR37","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R. E. Tarjan","year":"1972","unstructured":"R. E. Tarjan, Depth-first search and linear graph algorithms,SIAM Journal on Computing, 1:146?160, 1972.","journal-title":"SIAM Journal on Computing"},{"key":"CR38","volume-title":"Encyclopedia of Mathematics and Its Applications, volume 21","author":"W. Tutte","year":"1984","unstructured":"W. Tutte,Graph Theory, Encyclopedia of Mathematics and Its Applications, volume 21, Addison-Wesley, Reading, MA, 1984."},{"key":"CR39","volume-title":"Graphs, Groups, and Surfaces","author":"A. T. White","year":"1973","unstructured":"A. T. White,Graphs, Groups, and Surfaces, North-Holland, New York, 1973."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01192047.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01192047\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01192047","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T13:08:49Z","timestamp":1556629729000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01192047"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,11]]},"references-count":39,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1995,11]]}},"alternative-id":["BF01192047"],"URL":"https:\/\/doi.org\/10.1007\/bf01192047","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,11]]}}}