{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T14:25:28Z","timestamp":1726410328329},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642175138"},{"type":"electronic","value":"9783642175145"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-17514-5_32","type":"book-chapter","created":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T15:09:23Z","timestamp":1291388963000},"page":"375-386","source":"Crossref","is-referenced-by-count":0,"title":["Why Depth-First Search Efficiently Identifies Two and Three-Connected Graphs"],"prefix":"10.1007","author":[{"given":"Amr","family":"Elmasry","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"32_CR1","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BF02253293","volume":"30","author":"J. Ebert","year":"1983","unstructured":"Ebert, J.: st-Ordering the vertices of biconnected graphs. Computing\u00a030, 19\u201333 (1983)","journal-title":"Computing"},{"key":"32_CR2","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/0304-3975(76)90086-4","volume":"2","author":"S. Even","year":"1976","unstructured":"Even, S., Tarjan, R.E.: Computing an st-numbering. Theoretical Computer Science\u00a02, 339\u2013344 (1976)","journal-title":"Theoretical Computer Science"},{"key":"32_CR3","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R.E. Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM Journal on Computing\u00a01, 146\u2013159 (1972)","journal-title":"SIAM Journal on Computing"},{"key":"32_CR4","doi-asserted-by":"crossref","unstructured":"Elmasry, A., Mehlhorn, K., Schmidt, J.M.: A linear-time certifying triconnectivity algorithm for Hamiltonian graphs. Available at the second author\u2019s home page (2010)","DOI":"10.1007\/s00453-010-9481-2"},{"issue":"3","key":"32_CR5","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Dividing a graph into triconnected components. SIAM Journal on Computing\u00a02(3), 135\u2013158 (1973)","journal-title":"SIAM Journal on Computing"},{"key":"32_CR6","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press and McGraw-Hill (2001)"},{"key":"32_CR7","volume-title":"The Art of Computer Programming","author":"D. Knuth","year":"1997","unstructured":"Knuth, D.: The Art of Computer Programming, 3rd edn., vol.\u00a01. Addison-Wesley, Reading (1997)","edition":"3"},{"key":"32_CR8","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/S1385-7258(61)50045-5","volume":"23","author":"W. Tutte","year":"1961","unstructured":"Tutte, W.: A theory of 3-connected graphs. Indag. Math.\u00a023, 441\u2013455 (1961)","journal-title":"Indag. Math."},{"issue":"2","key":"32_CR9","first-page":"171","volume":"6","author":"R.E. Tarjan","year":"1976","unstructured":"Tarjan, R.E.: Edge-disjoint spanning trees and depth-first search. Algorithmica\u00a06(2), 171\u2013185 (1976)","journal-title":"Algorithmica"},{"issue":"4","key":"32_CR10","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J.E. Hopcroft","year":"1974","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Efficient planarity testing. Journal of the Association for Computing Machinery\u00a021(4), 549\u2013568 (1974)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"32_CR11","unstructured":"Elmasry, A., Mehlhorn, K., Schmidt, J.M.: Every DFS tree of a 3-connected graph contains a contractible edge. Available at the second author\u2019s home page (2010)"},{"key":"32_CR12","volume-title":"Computer and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computer and Intractability: A Guide to the Theory of NP-Completeness. W. Freeman, New York (1979)"},{"key":"32_CR13","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/BF01758778","volume":"7","author":"H. Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica\u00a07, 583\u2013596 (1992)","journal-title":"Algorithmica"},{"key":"32_CR14","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1137\/0222013","volume":"22","author":"J. Cheriyan","year":"1993","unstructured":"Cheriyan, J., Kao, M.Y., Thurimella, R.: Scan-first search and sparse certificates: an improved parallel algorithm for k-vertex connectivity. SIAM Journal on Computing\u00a022, 157\u2013174 (1993)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17514-5_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,14]],"date-time":"2021-11-14T11:32:10Z","timestamp":1636889530000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17514-5_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642175138","9783642175145"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17514-5_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}