On the ratio between the maximum weight of a perfect matching and the maximum weight of a matching

DOI10.1016/J.DAM.2021.05.009MaRDI QIDQ2032967zbMATH OpenOpenAlexFDO

Authors G. Mazzuoccolo, Lorenzo Mella

Publication date 14 June 2021

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

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

zbMATH Keywords

cubic graphmaximal matchingperfect matching

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• On the ratio between maximum weight perfect matchings and maximum weight matchings in grids
• The cost of perfection for matchings in graphs
• scientific article; zbMATH DE number 2114098
• An Optimum Lower Bound for the Weights of Maximum Weight Matching in Bipartite Graphs
• Pairs of disjoint matchings and related classes of graphs

Cites work

• Converting triangulations to quadrangulations
• On the ratio between maximum weight perfect matchings and maximum weight matchings in grids
• Randomly matchable graphs
• The cost of perfection for matchings in graphs

Cited in

(3)

• On the maximum 2-1 matching
• On the ratio between maximum weight perfect matchings and maximum weight matchings in grids
• The cost of perfection for matchings in graphs

This page was built for publication: On the ratio between the maximum weight of a perfect matching and the maximum weight of a matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2032967)