2026-07-23T21:03:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21130 2024-09-23T09:13:17Z ddc:004 open_access

Finding Perfect Matchings in Bridgeless Cubic Multigraphs Without Dynamic (2-)connectivity Gawrychowski, Paweł Wasylkiewicz, Mateusz perfect matching cubic graphs bridgeless graphs link-cut tree Petersen’s theorem, one of the earliest results in graph theory, states that every bridgeless cubic multigraph contains a perfect matching. While the original proof was neither constructive nor algorithmic, Biedl, Bose, Demaine, and Lubiw [J. Algorithms 38(1)] showed how to implement a later constructive proof by Frink in 𝒪(nlog⁴n) time using a fully dynamic 2-edge-connectivity structure. Then, Diks and Stańczyk [SOFSEM 2010] described a faster approach that only needs a fully dynamic connectivity structure and works in 𝒪(nlog²n) time. Both algorithms, while reasonable simple, utilize non-trivial (2-edge-)connectivity structures. We show that this is not necessary, and in fact a structure for maintaining a dynamic tree, e.g. link-cut trees, suffices to obtain a simple 𝒪(nlog n) time algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paweł Gawrychowski and Mateusz Wasylkiewicz 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.59 urn:nbn:de:0030-drops-211301 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.59 eng https://creativecommons.org/licenses/by/4.0/legalcode