{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:15Z","timestamp":1759639035598},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2010,12,8]],"date-time":"2010-12-08T00:00:00Z","timestamp":1291766400000},"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":[[2012,4]]},"DOI":"10.1007\/s00453-010-9481-2","type":"journal-article","created":{"date-parts":[[2010,12,7]],"date-time":"2010-12-07T15:18:11Z","timestamp":1291735091000},"page":"754-766","source":"Crossref","is-referenced-by-count":8,"title":["An O(n+m) Certifying Triconnnectivity Algorithm for\u00a0Hamiltonian Graphs"],"prefix":"10.1007","volume":"62","author":[{"given":"Amr","family":"Elmasry","sequence":"first","affiliation":[]},{"given":"Kurt","family":"Mehlhorn","sequence":"additional","affiliation":[]},{"given":"Jens M.","family":"Schmidt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,12,8]]},"reference":[{"key":"9481_CR1","first-page":"198","volume-title":"FOCS","author":"S. Alstrup","year":"2000","unstructured":"Alstrup, S., Brodal, G., Rauhe, T.: New data structures for orthogonal range searching. In: FOCS, pp.\u00a0198\u2013207 (2000)"},{"key":"9481_CR2","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0095-8956(87)90065-7","volume":"42","author":"K. Ando","year":"1987","unstructured":"Ando, K., Enomoto, H., Saito, A.: Contractible edges in 3-connected graphs. J. Comb. Theory, Ser. B 42, 87\u201393 (1987)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9481_CR3","first-page":"247","volume-title":"ESA","author":"U. Brandes","year":"2002","unstructured":"Brandes, U.: Eager st-ordering. In: ESA, pp. 247\u2013256 (2002)"},{"key":"9481_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03427-9","volume-title":"Computational Geometry: Algorithms and Applications","author":"M. Berg de","year":"1997","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications. Springer, Berlin (1997)"},{"key":"9481_CR5","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 web-page, February 2010"},{"issue":"3","key":"9481_CR6","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1137\/0204034","volume":"4","author":"S. Even","year":"1975","unstructured":"Even, S.: An algorithm for determining whether the connectivity of a graph is at least k. SIAM J. Comput. 4(3), 393\u2013396 (1975)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9481_CR7","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1137\/0209016","volume":"9","author":"Z. Galil","year":"1980","unstructured":"Galil, Z.: Finding the vertex connectivity of graphs. SIAM J. Comput. 9(1), 197\u2013199 (1980)","journal-title":"SIAM J. Comput."},{"key":"9481_CR8","first-page":"135","volume-title":"STOC","author":"H. Gabow","year":"1984","unstructured":"Gabow, H., Bentley, J., Tarjan, R.: Scaling and related techniques for geometry problems. In: STOC, pp. 135\u2013143 (1984)"},{"key":"9481_CR9","series-title":"LNCS","first-page":"77","volume-title":"Graph Drawing","author":"C. Gutwenger","year":"2000","unstructured":"Gutwenger, C., Mutzel, P.: A linear time implementation of SPQR-trees. In: Graph Drawing. LNCS, vol. 1984, pp. 77\u201390 (2000)"},{"issue":"2","key":"9481_CR10","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"H.N. Gabow","year":"1985","unstructured":"Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30(2), 209\u2013221 (1985)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9481_CR11","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"Hopcroft, J., Tarjan, R.E.: Efficient planarity testing. J. ACM 21(4), 549\u2013568 (1974)","journal-title":"J. ACM"},{"key":"9481_CR12","first-page":"1","volume":"8","author":"T. Imai","year":"1987","unstructured":"Imai, T., Asano, T.: Dynamic segment intersection with applications. J. ACM 8, 1\u201318 (1987)","journal-title":"J. ACM"},{"issue":"1","key":"9481_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s003730200000","volume":"18","author":"M. Kriesell","year":"2002","unstructured":"Kriesell, M.: A survey on contractible edges in graphs of a prescribed vertex connectivity. Graphs Comb. 18(1), 1\u201330 (2002)","journal-title":"Graphs Comb."},{"issue":"1","key":"9481_CR14","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF02122557","volume":"8","author":"N. Linial","year":"1988","unstructured":"Linial, N., Lov\u00e1sz, L., Wigderson, A.: Rubber bands, convex embeddings, and graph connectivity. Combinatorica 8(1), 91\u2013102 (1988)","journal-title":"Combinatorica"},{"key":"9481_CR15","series-title":"Multi-dimensional Searching and Computational Geometry","volume-title":"Data Structures and Efficient Algorithms","author":"K. Mehlhorn","year":"1984","unstructured":"Mehlhorn, K.: Data Structures and Efficient Algorithms, vol.\u00a03: Multi-dimensional Searching and Computational Geometry. Springer, Berlin (1984)"},{"key":"9481_CR16","author":"R. McConnell","year":"2010","unstructured":"McConnell, R., Mehlhorn, K., N\u00e4her, S., Schweitzer, P.: Certifying algorithms. Comput. Sci. Rev. (2010). doi: 10.1016\/j.cosrev.2010.09.009","journal-title":"Comput. Sci. Rev."},{"issue":"1","key":"9481_CR17","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/BF01191205","volume":"12","author":"G.L. Miller","year":"1992","unstructured":"Miller, G.L., Ramachandran, V.: A new graph triconnectivity algorithm and its parallelization. Combinatorica 12(1), 53\u201376 (1992)","journal-title":"Combinatorica"},{"key":"9481_CR18","doi-asserted-by":"crossref","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 7, 583\u2013596 (1992)","journal-title":"Algorithmica"},{"key":"9481_CR19","volume-title":"27th International Symposium on Theoretical Aspects of Computer Science (STACS\u201910)","author":"J.M. Schmidt","year":"2010","unstructured":"Schmidt, J.M.: Construction sequences and certifying 3-connectedness. In: 27th International Symposium on Theoretical Aspects of Computer Science (STACS\u201910), Nancy, France (2010). http:\/\/drops.dagstuhl.de\/portals\/extern\/index.php?conf=STACS10"},{"key":"9481_CR20","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1002\/jgt.3190050403","volume":"5","author":"C. Thomassen","year":"1981","unstructured":"Thomassen, C.: Nonseparating cycles in k-connected graphs. J. Graph. Theory 5, 351\u2013354 (1981)","journal-title":"J. Graph. Theory"},{"key":"9481_CR21","doi-asserted-by":"crossref","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. 23, 441\u2013455 (1961)","journal-title":"Indag. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9481-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9481-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9481-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T21:51:39Z","timestamp":1559857899000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9481-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12,8]]},"references-count":21,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["9481"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9481-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12,8]]}}}