Maximum weight edge-constrained matchings

DOI10.1016/j.dam.2007.08.021zbMath1135.68026OpenAlexW2082143173MaRDI QIDQ2476253

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

NP-completenessmaximum weight matching3-degree bipartite graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) 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) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Graph matching problems and the NP-hardness of sortedness constraints ⋮ Integrality gaps for colorful matchings ⋮ Minimum <scp>color‐degree</scp> perfect b‐matchings ⋮ Maximum Induced Matchings in Grids

Cites Work

• Matching theory
• On generating all maximal independent sets
• Transversals of latin squares and their generalizations
• Three short proofs in graph theory
• Coloured matchings in bipartite graphs
• On graphs with polynomially solvable maximum-weight clique problem
• Some Matching Problems for Bipartite Graphs
• Algorithm Theory - SWAT 2004
• Maximum matching and a polyhedron with 0,1-vertices
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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