Faster algorithm for finding maximum 1-restricted simple 2-matchings

DOI10.1007/s00453-023-01148-6MaRDI QIDQ6119828

Stepan Artamonov, Maxim A. Babenko

Publication date: 25 March 2024

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

polynomial algorithmmin-max formularestricted matchingsblocking augmentations

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Maximum cardinality 1-restricted simple 2-matchings
• Matching theory
• A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two
• Packing paths of length at least two
• Maximum skew-symmetric flows and matchings
• Faster algorithm for finding maximum 1-restricted simple 2-matchings
• The k‐piece packing problem
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Faster algorithm for finding maximum 1-restricted simple 2-matchings