Maximum weight edge-constrained matchings

DOI10.1016/j.dam.2007.08.021zbMath1135.68026MaRDI 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-completeness; maximum weight matching; 3-degree bipartite graph

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

90C59: Approximation methods and heuristics in mathematical programming

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Maximum Induced Matchings in Grids, Graph matching problems and the NP-hardness of sortedness constraints, Integrality gaps for colorful matchings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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