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

DOI10.1016/j.dam.2016.02.017zbMath1337.05088OpenAlexW2295223672MaRDI QIDQ290099

Bernard Ries, Guilherme Dias 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

zbMATH Keywords

matchinggrid

Mathematics Subject Classification ID

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

Related Items (1)

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

Uses Software

• Blossom-Quad

Cites Work

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

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