{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:04:23Z","timestamp":1725663863100},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540571827"},{"type":"electronic","value":"9783540479277"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57182-5_42","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T07:11:11Z","timestamp":1330240271000},"page":"506-516","source":"Crossref","is-referenced-by-count":0,"title":["Efficient parallel graph algorithms based on open ear decomposition"],"prefix":"10.1007","author":[{"given":"Louis","family":"Ibarra","sequence":"first","affiliation":[]},{"given":"Dana","family":"Richards","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"42_CR1","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF02579320","volume":"7","author":"R. Anderson","year":"1987","unstructured":"R. Anderson. A parallel algorithm for the maximal path problem. Combinatorica, 7:315\u2013326, 1987.","journal-title":"Combinatorica"},{"key":"42_CR2","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0190(87)90105-0","volume":"24","author":"R. Anderson","year":"1987","unstructured":"R. Anderson and E. Mayr. Parallelism and the maximal path problem. Information Processing Letters, 24:121\u2013126, 1987.","journal-title":"Information Processing Letters"},{"key":"42_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph Theory with Applications","author":"J. Bondy","year":"1976","unstructured":"J. Bondy and U. Murty. Graph Theory with Applications. North-Holland, Amsterdam, 1976."},{"key":"42_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0890-5401(91)90019-X","volume":"92","author":"R. Cole","year":"1991","unstructured":"R. Cole and U. Vishkin. Approximate parallel scheduling ii: Applications to logarithmic-time optimal parallel graph algorithms. Information and Computation, 92:1\u201347, 1991.","journal-title":"Information and Computation"},{"key":"42_CR5","volume-title":"Introduction to Algorithms","author":"T. H. Corman","year":"1990","unstructured":"T. H. Corman, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press and McGraw-Hill Book Co., Cambridge, MA and New York, NY, 1990."},{"key":"42_CR6","series-title":"Lecture Notes in Computer Science 372","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/BFb0035771","volume-title":"Proc. 16th ICALP","author":"D. Fussell","year":"1989","unstructured":"D. Fussell, V. Ramachandran, and R. Thurimella. Finding triconnected components by local replacements. In Proc. 16th ICALP, Lecture Notes in Computer Science 372, pages 379\u2013393, New York, 1989. Springer-Verlag."},{"issue":"3","key":"42_CR7","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 search trees in planar graphs. SIAM Journal on Computing, 17(3):486\u2013491, 1988.","journal-title":"SIAM Journal on Computing"},{"unstructured":"L. Ibarra and D. Richards. Efficient parallel algorithms based on open ear decompositions. Submitted to Parallel Computing.","key":"42_CR8"},{"key":"42_CR9","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1016\/0022-0000(91)90004-O","volume":"42","author":"A. Kanevsky","year":"1991","unstructured":"A. Kanevsky and V. Ramachandran. Improved algorithms for four-connectivity. Journal of Computer and System Sciences, 42:288\u2013306, 1991.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"42_CR10","first-page":"128","volume":"20","author":"S. Khuller","year":"1989","unstructured":"S. Khuller. Ear decompositions. SigAct News, 20(1):128, 1989.","journal-title":"SigAct News"},{"doi-asserted-by":"crossref","unstructured":"S. Khuller and B. Schieber. Efficient parallel algorithms for testing connectivity and finding disjoint s-t paths in graphs. In Proc. 30th Annual IEEE Symp. on Foundations of Computer Science, pages 288\u2013293, 1989.","key":"42_CR11","DOI":"10.1109\/SFCS.1989.63492"},{"doi-asserted-by":"crossref","unstructured":"L. Lov\u00e1sz. Computing ears and branchings in parallel. In Proc. 26th Annual IEEE Symp. on Foundations of Computer Science, pages 464\u2013467, 1985.","key":"42_CR12","DOI":"10.1109\/SFCS.1985.16"},{"key":"42_CR13","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0304-3975(86)90153-2","volume":"47","author":"Y. Maon","year":"1986","unstructured":"Y. Maon, B. Schieber, and U. Vishkin. Parallel ear decomposition search (eds) and stnumbering in graphs. Theoretical Computer Science, 47:277\u2013298, 1986.","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"G. L. Miller and V. Ramachandran. A new graph triconnectivity algorithm and its parallelization. In Proc. 19th Annual ACM Symp. on Theory of Computing, pages 335\u2013344, 1987.","key":"42_CR14","DOI":"10.1145\/28395.28431"},{"doi-asserted-by":"crossref","unstructured":"V. Ramachandran and J. Reif. An optimal parallel algorithm for graph planarity. In Proc. 30th Annual IEEE Symp. on Foundations of Computer Science, pages 282\u2013287, 1989.","key":"42_CR15","DOI":"10.1109\/SFCS.1989.63491"},{"key":"42_CR16","first-page":"33","volume-title":"Lecture Notes in Computer Science 319","author":"V. Ramachandran","year":"1988","unstructured":"V. Ramachandran and U. Vishkin. Efficient parallel triconnectivity in logarithmic time. In 3rd Aegean Workshop on Computing, Lecture Notes in Computer Science 319, pages 33\u201342, New York, 1988. Springer-Verlag."},{"key":"42_CR17","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\u2013123, 1988.","journal-title":"Information Processing Letters"},{"issue":"4","key":"42_CR18","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R. E. Tarjan","year":"1985","unstructured":"R. E. Tarjan and U. Vishkin. An efficient parallel biconnectivity algorithm. SIAM Journal on Computing, 14(4):862\u2013874, 1985.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"42_CR19","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0196-6774(83)90033-0","volume":"4","author":"U. Vishkin","year":"1983","unstructured":"U. Vishkin. Implementation of simultaneous memory address access in models that forbid it. Journal of Algorithms, 4(1):45\u201350, 1983.","journal-title":"Journal of Algorithms"},{"key":"42_CR20","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1090\/S0002-9947-1932-1501641-2","volume":"34","author":"H. Whitney","year":"1932","unstructured":"H. Whitney. Non-separable and planar graphs. Transactions of the American Mathematical Society, 34:339\u2013362, 1932.","journal-title":"Transactions of the American Mathematical Society"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1993"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57182-5_42.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:08:42Z","timestamp":1605629322000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57182-5_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540571827","9783540479277"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-57182-5_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}