{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:36:36Z","timestamp":1775054196516,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642112652","type":"print"},{"value":"9783642112669","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11266-9_27","type":"book-chapter","created":{"date-parts":[[2009,12,7]],"date-time":"2009-12-07T14:04:58Z","timestamp":1260194698000},"page":"321-333","source":"Crossref","is-referenced-by-count":5,"title":["Perfect Matching for Biconnected Cubic Graphs in O(n log2 n) Time"],"prefix":"10.1007","author":[{"given":"Krzysztof","family":"Diks","sequence":"first","affiliation":[]},{"given":"Piotr","family":"Stanczyk","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0020-0190(91)90195-N","volume":"37","author":"H. Alt","year":"1991","unstructured":"Alt, H., Blum, N., Mehlhorn, K., Paul, M.: Computing a Maximum Cardinality Matching in a Bipartite Graph in Time $O(n^{1.5}\\sqrt{m\/\\log n})$ . Information Processing Letters\u00a037, 237\u2013240 (1991)","journal-title":"Information Processing Letters"},{"key":"27_CR2","unstructured":"Biedl, T.C.: Linear Reductions of Maximum Matching. In: SODA 2001, pp. 825\u2013826 (2001)"},{"key":"27_CR3","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1006\/jagm.2000.1132","volume":"38","author":"T. Biedl","year":"2001","unstructured":"Biedl, T., Bose, P., Demaine, E., Lubiw, A.: Efficient Algorithms for Petersen\u2019s Matching Theorem. Journal of Algorithms\u00a038, 110\u2013134 (2001)","journal-title":"Journal of Algorithms"},{"issue":"4","key":"27_CR4","doi-asserted-by":"publisher","first-page":"491","DOI":"10.2307\/1967699","volume":"27","author":"O. Frink","year":"1926","unstructured":"Frink, O.: A Proof of Petersen\u2019s Theorem. The Annals of Mathematics, Series\u00a02\u00a027(4), 491\u2013493 (1926)","journal-title":"The Annals of Mathematics, Series\u00a02"},{"key":"27_CR5","unstructured":"Henzinger, M., King, V.: Fully Dynamic 2-Edge Connectivity Algorithm in Polylogarithmic Time per Operation. Technical Note, Digital Equipment Corp., Systems Research Ctr. (June 12, 1997)"},{"key":"27_CR6","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J. Holm","year":"2001","unstructured":"Holm, J., De Lichtenserg, K., Thorup, M.: Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge and Biconnectivity. Journal of the ACM (JACM)\u00a048, 723\u2013760 (2001)","journal-title":"Journal of the ACM (JACM)"},{"key":"27_CR7","volume-title":"Matching Theory","author":"L. Lovasz","year":"1986","unstructured":"Lovasz, L., Plummer, M.D.: Matching Theory. North-Holland Publishing Co., Amsterdam (1986)"},{"key":"27_CR8","first-page":"17","volume-title":"Proceedings of FOCS 1980","author":"S. Micali","year":"1980","unstructured":"Micali, S., Vazirani, V.V.: An $O(\\sqrt{n}m)$ Algorithm for Finding Maximum Matching in General Graphs. In: Proceedings of FOCS 1980, pp. 17\u201327. IEEE, Los Alamitos (1980)"},{"key":"27_CR9","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF02392606","volume":"15","author":"J. Petersen","year":"1891","unstructured":"Petersen, J.: Die Theorie der regul\u00e4ren Graphs. Acta Mathematica\u00a015, 193\u2013220 (1891)","journal-title":"Acta Mathematica"},{"key":"27_CR10","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198501626.001.0001","volume-title":"Fast Parallel Algorithms for Graph Matching Problem","author":"M. Karpi\u0144ski","year":"1998","unstructured":"Karpi\u0144ski, M., Rytter, W.: Fast Parallel Algorithms for Graph Matching Problem. Oxford University Press, Oxford (1998)"},{"key":"27_CR11","volume-title":"Combinatorial Optimization \u2013 Polyhedra and Efficiency. Parts\u00a0II and\u00a0III","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization \u2013 Polyhedra and Efficiency. Parts\u00a0II and\u00a0III. Springer, Berlin (2003)"},{"issue":"3","key":"27_CR12","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1137\/S0097539796299266","volume":"28","author":"A. Schrijver","year":"1999","unstructured":"Schrijver, A.: Bipartite Edge Coloring in O(\u0394m) Time. SIAM Journal on Computing\u00a028(3), 841\u2013846 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"Sleator, D.D., Tarjan, R.E.: A Data Structure for Dynamic Trees. In: Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing, pp. 114\u2013122 (1981)","DOI":"10.1145\/800076.802464"},{"key":"27_CR14","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R.E. Tarjan","year":"1983","unstructured":"Tarjan, R.E.: Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1983)"},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Near-Optimal Fully-Dynamic Graph Connectivity. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 343\u2013350 (2000)","DOI":"10.1145\/335305.335345"},{"key":"27_CR16","unstructured":"Thorup, M.: Decremental Dynamic Connectivity. In: Proceedings of the 8th\u00a0ACM Symposium on Discrete Algorithms (SODA), pp. 305\u2013313 (1997)"},{"key":"27_CR17","unstructured":"Mucha, M.: Finding Maximum Matchings via Gaussian Elimination. PhD Thesis, Warsaw University, Faculty of Mathematics, Informatics and Mechanics"},{"key":"27_CR18","unstructured":"Harvey, N.J.A.: Algebraic Algorithms for Matching and Matroid Problems. Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology"},{"issue":"4","key":"27_CR19","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1145\/234782.234783","volume":"27","author":"R. Greenlaw","year":"1995","unstructured":"Greenlaw, R., Petreschi, R.: Cubic Graphs. ACM Computing Surveys (CSUR)\u00a027(4), 471\u2013495 (1995)","journal-title":"ACM Computing Surveys (CSUR)"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2010: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11266-9_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,18]],"date-time":"2024-03-18T01:30:17Z","timestamp":1710725417000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11266-9_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642112652","9783642112669"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11266-9_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}