On improving matchings in trees, via bounded-length augmentations

DOI10.1016/J.DAM.2018.05.021zbMath1398.05157OpenAlexW2725137878WikidataQ129739180 ScholiaQ129739180MaRDI QIDQ1801054

Julien Bensmail, Valentin Garnero, Nicolas Nisse

Publication date: 26 October 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2018.05.021

zbMATH Keywords

treesmaximum matchingsbounded-length augmentations

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Recovery of disrupted airline operations using \(k\)-maximum matching in graphs
• Linear-Time Approximation for Maximum Weight Matching
• TWO THEOREMS IN GRAPH THEORY
• Paths, Trees, and Flowers
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: On improving matchings in trees, via bounded-length augmentations