On the ratio between maximum weight perfect matchings and maximum weight matchings in grids

DOI10.1016/J.DAM.2016.02.017zbMATH Open1337.05088OpenAlexW2295223672MaRDI QIDQ290099FDOQ290099

Authors: Bernard Ries, Guilherme D. Da Fonseca, Diana Sasaki 

Publication date: 1 June 2016

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

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

Recommendations

• On the ratio between the maximum weight of a perfect matching and the maximum weight of a matching
• The cost of perfection for matchings in graphs
• scientific article; zbMATH DE number 2114098
• Maximum Induced Matchings in Grids
• Optimum matchings in weighted bipartite graphs

zbMATH Keywords

gridmatching

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• TWO THEOREMS IN GRAPH THEORY
• Converting triangulations to quadrangulations
• Blossom-Quad: a non-uniform quadrilateral mesh generator using a minimum-cost perfect-matching algorithm
• The cost of perfection for matchings in graphs

Cited In (2)

• On the ratio between the maximum weight of a perfect matching and the maximum weight of a matching
• The cost of perfection for matchings in graphs

Uses Software

• Blossom-Quad

This page was built for publication: On the ratio between maximum weight perfect matchings and maximum weight matchings in grids

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