A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges

DOI10.1016/j.ipl.2021.106146OpenAlexW3169464877MaRDI QIDQ2032181

Mateusz Wasylkiewicz, Katarzyna E. Paluch

Publication date: 16 June 2021

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2012.15775

zbMATH Keywords

graph algorithmsmaximum weight \(b\)-matchingtriangle-free 2-matchingrestricted 2-matchinghalf-edges

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids

Cites Work

• Unnamed Item
• Unnamed Item
• An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach
• A simple algorithm for finding a maximum triangle-free \(2\)-matching in subcubic graphs
• Combinatorial algorithms for matchings, even factors and square-free 2-factors
• Weighted restricted 2-matching
• A matching problem with side conditions
• A fast scaling algorithm for the weighted triangle-free 2-matching problem
• Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs
• Polyhedron of triangle-free simple 2-matchings in subcubic graphs
• Excluded \(t\)-factors in bipartite graphs: a unified framework for nonbipartite matchings and restricted 2-matchings
• Finding maximum square-free 2-matchings in bipartite graphs
• Maximum Cardinality Simple 2-matchings in Subcubic Graphs
• A Weighted k_{t, t}-Free t-Factor Algorithm for Bipartite Graphs
• On Maximum Cost $K_{t,t}$‐Free t‐Matchings of Bipartite Graphs
• Restricted b-Matchings in Degree-Bounded Graphs
• Triangle-Free 2-Matchings Revisited
• Perfect triangle-free 2-matchings
• Weighted Triangle-Free 2-Matching Problem with Edge-Disjoint Forbidden Triangles

This page was built for publication: A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges