{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:40:03Z","timestamp":1742600403812,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540603139"},{"type":"electronic","value":"9783540449133"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60313-1_130","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T18:15:54Z","timestamp":1330280154000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On mixed connectivity certificates"],"prefix":"10.1007","author":[{"given":"Shimon","family":"Even","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gene","family":"Itkis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergio","family":"Rajsbaum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"B. Awerbuch and D. Peleg, \u201cNetwork synchronization with polylogarithmic overhead\u201d, in FOCS, 1990, pp. 514\u2013522.","DOI":"10.1109\/FSCS.1990.89572"},{"key":"1_CR2","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1016\/0196-6774(88)90015-6","volume":"9","author":"J. Cheriyan","year":"1988","unstructured":"J. Cheriyan and S. N. Maheshwari, \u201cFinding nonseparating induced cycles and independent spanning trees in 3-connected graphs\u201d, J. Algorithms, 9, 1988, pp. 507\u2013537.","journal-title":"J. Algorithms"},{"issue":"1","key":"1_CR3","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1137\/0222013","volume":"22","author":"J. Cheriyan","year":"1993","unstructured":"J. Cheriyan, M.-Y. Kao, R. Thurimella, \u201cScan-first search and sparse certificates: an improved parallel algorithm for k-vertex connectivity\u201d, SIAM J. of Computing, 22(1), 1993, pp. 157\u2013174.","journal-title":"SIAM J. of Computing"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"G. B. Dantzig and D. R. Fulkerson, \u201cOn the Max-Flow Min-Cut Theorem of networks\u201d, Linear Inequalities and Related Systems, Annals of Math. Study, 38, Princeton University Press, 1956, pp.215\u2013221.","DOI":"10.1515\/9781400881987-013"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"D. Eppstein, Z. Galil, G. F. Italiano, A. Nissenzweig, \u201cSparsification \u2014 a technique for speeding up dynamic algorithms\u201d, FOCS, 1992, pp. 60\u201369.","DOI":"10.1109\/SFCS.1992.267818"},{"issue":"3","key":"1_CR6","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1002\/jgt.3190170302","volume":"17","author":"A. Frank","year":"1993","unstructured":"A. Frank, T. Ibaraki, H. Nagamochi, \u201cOn sparse subgraphs preserving connectivity properties\u201d, J. of Graph Theory, 17(3), 1993, pp. 275\u2013281.","journal-title":"J. of Graph Theory"},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"H. Gabow, \u201cA matroid approach to finding edge connectivity and packing arborescences\u201d, STOC, 1991, pp. 112\u2013132.","DOI":"10.1145\/103418.103436"},{"key":"1_CR8","first-page":"198","volume-title":"Computers and intractability, a guide to the theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson, Computers and intractability, a guide to the theory of NP-completeness, Freeman, San Francisco, 1979, p. 198."},{"issue":"1","key":"1_CR9","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0890-5401(88)90016-8","volume":"79","author":"A. Itai","year":"1988","unstructured":"A. Itai and M. Rodeh, \u201cThe Multi-Tree Approach to Reliability in Distributed Networks\u201d, Information and Computation, 79(1), 1988, pp. 3\u201359.","journal-title":"Information and Computation"},{"key":"1_CR10","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/BF01304933","volume":"XXIII","author":"W. Mader","year":"1972","unstructured":"W. Mader, \u201c\u00dcber minimal n-fach zusammenh\u00e4ngende, unendliche Graphen und ein Extremalproblem,\u201d Arch. Mat., Vol. XXIII, 1972, pp. 553\u2013560.","journal-title":"Arch. Mat."},{"key":"1_CR11","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/BF01432512","volume":"205","author":"W. Mader","year":"1973","unstructured":"W. Mader, \u201cGrad und lokaler Zusammenhang in endlichen Graphen,\u201d Math. Ann., Vol. 205, 1973, pp. 9\u201311.","journal-title":"Math. Ann."},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"W. Mader, \u201cConnectivity and edge-connectivity in finite graphs,\u201d in Surveys on Combinatorics, (B. Bollobas, ed.), London Math. Soc. Lecture Note Series, Vol. 38, 1979, pp. 293\u2013309.","DOI":"10.1017\/CBO9780511662133.005"},{"key":"1_CR13","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/BF01758778","volume":"7","author":"H. Nagamochi","year":"1992","unstructured":"H. Nagamochi and T. Ibaraki, \u201cA Linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-conneceted graph,\u201d Algorithmica, 7, 1992, pp. 583\u2013596.","journal-title":"Algorithmica"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"R. Thurimella, \u201cSub-linear Distributed Algorithms for sparse certificates and Biconnected Components,\u201d to appear in Proc. of the 14th ACM Symposium on Principles of Distributed Computing, August 1995.","DOI":"10.1145\/224964.224968"},{"key":"1_CR15","first-page":"104","volume-title":"Theory of Finite Graphs","author":"A. A. Zykov","year":"1969","unstructured":"A. A. Zykov, Theory of Finite Graphs, (in Russian), Nauka, Novosibirsk, 1969, see pp. 104\u2013105."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '95"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60313-1_130","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:59:40Z","timestamp":1742597980000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60313-1_130"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540603139","9783540449133"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-60313-1_130","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}