{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,5]],"date-time":"2024-06-05T15:40:04Z","timestamp":1717602004660},"reference-count":44,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[1993,12,1]],"date-time":"1993-12-01T00:00:00Z","timestamp":754704000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":7168,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[1993,12]]},"DOI":"10.1016\/0022-0000(93)90042-u","type":"journal-article","created":{"date-parts":[[2003,12,4]],"date-time":"2003-12-04T12:01:00Z","timestamp":1070539260000},"page":"459-500","source":"Crossref","is-referenced-by-count":11,"title":["Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs"],"prefix":"10.1016","volume":"47","author":[{"given":"Ming-Yang","family":"Kao","sequence":"first","affiliation":[]},{"given":"Philip N.","family":"Klein","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0022-0000(93)90042-U_BIB1","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0196-6774(89)90017-5","article-title":"A simple tree contraction algorithm","volume":"10","author":"Abrahamson","year":"1989","journal-title":"J. Algorithms"},{"key":"10.1016\/0022-0000(93)90042-U_BIB2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02122548","article-title":"A random NC algorithm for depth first search","volume":"8","author":"Aggarwal","year":"1988","journal-title":"Combinatorica"},{"key":"10.1016\/0022-0000(93)90042-U_BIB3","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1137\/0219025","article-title":"Parallel depth-first search in general directed graphs","volume":"19","author":"Aggarwal","year":"1990","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0022-0000(93)90042-U_BIB4","series-title":"The Design and Analysis of Computer Algorithms","author":"Aho","year":"1974"},{"key":"10.1016\/0022-0000(93)90042-U_BIB5","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1007\/BF01759076","article-title":"Deterministic parallel list ranking","volume":"6","author":"Anderson","year":"1991","journal-title":"Algorithmica"},{"key":"10.1016\/0022-0000(93)90042-U_BIB6","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1137\/0218035","article-title":"Cascading divide-and-conquer: A technique for designing parallel algorithms","volume":"18","author":"Atallah","year":"1989","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0022-0000(93)90042-U_BIB7","series-title":"Graph Theory with Applications","author":"Bondy","year":"1976"},{"key":"10.1016\/0022-0000(93)90042-U_BIB8","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/BF01762121","article-title":"The accelerated centroid decomposition technique for optimal tree evaluation in logarithmic time","volume":"3","author":"Cole","year":"1988","journal-title":"Algorithmica"},{"key":"10.1016\/0022-0000(93)90042-U_BIB9","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1016\/0890-5401(89)90036-9","article-title":"Faster optimal prefix sums and list ranking","volume":"81","author":"Cole","year":"1989","journal-title":"Inform. and Comput."},{"key":"10.1016\/0022-0000(93)90042-U_BIB10","series-title":"Proceedings, 16th International Colloquium on Automata, Languages, and Programming","first-page":"379","article-title":"Findingtriconnected components by local replacements","author":"Fussell","year":"1989"},{"key":"10.1016\/0022-0000(93)90042-U_BIB11","series-title":"Proceedings, 28th Annual IEEE Symposium on Foundations of Computer Science","first-page":"238","article-title":"A parallel algorithm for finding a separator in planar graphs","author":"Gazit","year":"1987"},{"key":"10.1016\/0022-0000(93)90042-U_BIB12","series-title":"Concurrent Computations: Algorithms, Architecture, and Technology","first-page":"139","article-title":"Optimal tree contraction in the EREW model","author":"Gazit","year":"1988"},{"key":"10.1016\/0022-0000(93)90042-U_BIB13","series-title":"Proceedings, 6th Conference on Foundations of Software Technology and Theoretical Computer Science","first-page":"453","article-title":"An optimal parallel algorithm for dynamic expression evaluation and its applications","volume":"Vol. 241","author":"Gibbons","year":"1986"},{"key":"10.1016\/0022-0000(93)90042-U_BIB14","series-title":"Graph Theory","author":"Harary","year":"1969"},{"key":"10.1016\/0022-0000(93)90042-U_BIB15","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1137\/0217028","article-title":"A nearly optimal parallel algorithm for constructing depth first spanning trees in planar graphs","volume":"17","author":"He","year":"1988","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0022-0000(93)90042-U_BIB16","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1109\/31.1743","article-title":"Parallel algorithms for planar graphs and related problems","volume":"35","author":"Ja'Ja","year":"1988","journal-title":"IEEE Trans. Circuits Systems"},{"key":"10.1016\/0022-0000(93)90042-U_BIB17","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1016\/0022-0000(91)90004-O","article-title":"Improved algorithms for graph four-connectivity","volume":"42","author":"Kanevsky","year":"1991","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0022-0000(93)90042-U_BIB18","series-title":"Proceedings, 3rd Aegean Workshop on Computing","first-page":"53","article-title":"All graphs have cycle separators and planar directed depth-first search is in DNC","volume":"Vol. 319","author":"Kao","year":"1988"},{"key":"10.1016\/0022-0000(93)90042-U_BIB19","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0222032","article-title":"Linear-processor NC algorithms for planar directed graphs I. Strongly connected components","volume":"22","author":"Kao","year":"1993","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0022-0000(93)90042-U_BIB20","series-title":"Proceedings, 21st Annual ACM Symposium on Theory of Computing","first-page":"286","article-title":"Local reorientation, global order, and planar topology","author":"Kao","year":"1989"},{"key":"10.1016\/0022-0000(93)90042-U_BIB21","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1137\/0222033","article-title":"Linear-processor NC algorithms for planar directed graphs. II. Directed spanning trees","volume":"22","author":"Kao","year":"1993","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0022-0000(93)90042-U_BIB22","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1016\/0022-0000(88)90006-2","article-title":"An efficient parallel algorithm for planarity","volume":"37","author":"Klein","year":"1988","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0022-0000(93)90042-U_BIB23","series-title":"Proceedings, 3rd Agean Workshop on Computing: VLSI Algorithms and Architectures","first-page":"101","article-title":"Optimal parallel evaluation of tree-structured computations by raking","volume":"Vol. 319","author":"Kosaraju","year":"1988"},{"key":"10.1016\/0022-0000(93)90042-U_BIB24","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1145\/322217.322232","article-title":"Parallel prefix computation","volume":"27","author":"Ladner","year":"1980","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0022-0000(93)90042-U_BIB25","series-title":"Fast parallel algorithms for planar directed graphs","author":"Lingas","year":"1989"},{"key":"10.1016\/0022-0000(93)90042-U_BIB26","first-page":"177","article-title":"A separator theorem for planar graphs","volume":"36","author":"Lipton","year":"1979","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"10.1016\/0022-0000(93)90042-U_BIB27","series-title":"Proceedings, 26th Annual IEEE Symposium on Foundations of Computer Science","first-page":"464","article-title":"Computing ears and branchings","author":"Lovasz","year":"1985"},{"key":"10.1016\/0022-0000(93)90042-U_BIB28","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0304-3975(86)90153-2","article-title":"Parallel ear decomposition search (EDS) and st numbering in graphs","volume":"47","author":"Maon","year":"1986","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0022-0000(93)90042-U_BIB29","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0022-0000(86)90030-9","article-title":"Finding small simple cycle separators for 2-connected planar graphs","volume":"32","author":"Miller","year":"1986","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0022-0000(93)90042-U_BIB30","series-title":"Proceedings, 30th Annual IEEE Symposium on Foundations of Computer Science","first-page":"112","article-title":"Flow in planar graphs with multiple sources and sinks","author":"Miller","year":"1989"},{"key":"10.1016\/0022-0000(93)90042-U_BIB31","series-title":"Proceedings, 19th Annual ACM Symposium on Theory of Computing","first-page":"335","article-title":"A new graph triconnectivity algorithm and its parallelization","author":"Miller","year":"1987"},{"key":"10.1016\/0022-0000(93)90042-U_BIB32","series-title":"Proceedings, 26th Annual IEEE Symposium on Foundations of Computer Science","first-page":"478","article-title":"Parallel tree contractions and its applications","author":"Miller","year":"1985"},{"key":"10.1016\/0022-0000(93)90042-U_BIB33","first-page":"47","article-title":"Parallel tree contraction. Part I. Fundamentals","volume":"Vol. 5","author":"Miller","year":"1989"},{"key":"10.1016\/0022-0000(93)90042-U_BIB34","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1016\/0022-0000(89)90013-5","article-title":"Fast and efficient solution of path algebra problems","volume":"38","author":"Pan","year":"1989","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0022-0000(93)90042-U_BIB35","series-title":"Proceedings, 30th Annual IEEE Symposium on Foundations of Computer Science","first-page":"282","article-title":"An optimal parallel algorithm for graph planarity","author":"Ramachandran","year":"1989"},{"key":"10.1016\/0022-0000(93)90042-U_BIB36","series-title":"Proceedings, 3rd Aegean Workshop on Computing","first-page":"33","article-title":"Efficient parallel triconnectivity in logarithmic time","volume":"Vol. 319","author":"Ramachandran","year":"1988"},{"key":"10.1016\/0022-0000(93)90042-U_BIB37","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0190(85)90024-9","article-title":"Depth-first search is inherently sequential","volume":"20","author":"Reif","year":"1985","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0022-0000(93)90042-U_BIB38","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","article-title":"An O(log n) parallel connectivity algorithm","volume":"3","author":"Shiloach","year":"1982","journal-title":"J. Algorithms"},{"key":"10.1016\/0022-0000(93)90042-U_BIB39","doi-asserted-by":"crossref","first-page":"814","DOI":"10.1137\/0215058","article-title":"Parallel algorithms for depth first search. I. Planar graphs","volume":"15","author":"Smith","year":"1986","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0022-0000(93)90042-U_BIB40","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1137\/0220045","article-title":"Parallel transitive closure and point location in planar structures","volume":"20","author":"Tamassia","year":"1991","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0022-0000(93)90042-U_BIB41","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","article-title":"Depth-first search and linear graph algorithms","volume":"1","author":"Tarjan","year":"1972","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0022-0000(93)90042-U_BIB42","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","article-title":"An efficient parallel biconnectivity algorithm","volume":"14","author":"Tarjan","year":"1985","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0022-0000(93)90042-U_BIB43","series-title":"Proceedings, 3rd Aegean Workshop on Computing","first-page":"149","article-title":"Separation pair detection","volume":"Vol. 319","author":"Fussell","year":"1988"},{"key":"10.1016\/0022-0000(93)90042-U_BIB44","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1090\/S0002-9947-1932-1501641-2","article-title":"Non-separable and planar graphs","volume":"34","author":"Whitney","year":"1932","journal-title":"Trans. Amer. Math. Soc."}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:002200009390042U?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:002200009390042U?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T13:58:15Z","timestamp":1550325495000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/002200009390042U"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,12]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1993,12]]}},"alternative-id":["002200009390042U"],"URL":"https:\/\/doi.org\/10.1016\/0022-0000(93)90042-u","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[1993,12]]}}}