Maximum weight edge-constrained matchings

DOI10.1016/J.DAM.2007.08.021MaRDI QIDQ2476253zbMATH OpenOpenAlexFDO

Authors Irena Rusu

Publication date 18 March 2008

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

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

zbMATH Keywords

3-degree bipartite graphmaximum weight matchingNP-completeness

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Constrained weighted matchings and edge coverings in graphs
• scientific article; zbMATH DE number 795216
• An unfeasible matching problem
• Constrained matching problems in bipartite graphs
• Maximum weight induced matching in some subclasses of bipartite graphs

Cites work

• Algorithm Theory - SWAT 2004
• Coloured matchings in bipartite graphs
• scientific article; zbMATH DE number 3551893 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1229733 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Matching theory
• Maximum matching and a polyhedron with 0,1-vertices
• On generating all maximal independent sets
• On graphs with polynomially solvable maximum-weight clique problem
• Some Matching Problems for Bipartite Graphs
• Three short proofs in graph theory
• Transversals of latin squares and their generalizations

Cited in

(17)

• The complexity of matching with bonds
• Constrained weighted matchings and edge coverings in graphs
• The \textsc{WeightedCircuitsLmax} constraint
• Maximum matching and kernelization of edge dominating set
• Approximation algorithms for NMR spectral peak assignment.
• Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles
• Graph matching problems and the NP-hardness of sortedness constraints
• Integrality gaps for colorful matchings
• scientific article; zbMATH DE number 1945156 (Why is no real title available?)
• Maximum Induced Matchings in Grids
• Structure of conflict graphs in constraint alignment problems and algorithms
• On the maximum edge-pair embedding bipartite matching
• On the maximum edge-pair embedding bipartite matching
• Some graph optimization problems with weights satisfying linear constraints
• On a max-min problem concerning weights of edges
• Minimum <scp>color‐degree</scp> perfect b‐matchings
• The maximum fuzzy weighted matching models and hybrid genetic algorithm

This page was built for publication: Maximum weight edge-constrained matchings

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