The minimum maximal k-partial-matching problem

DOI10.1007/S11590-012-0531-3MaRDI QIDQ395867zbMATH OpenOpenAlexFDO

Authors Ignacio Garcia-Vargas, Raouf Senhadji-Navarro

Publication date 30 January 2014

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://idus.us.es/handle//11441/90799

zbMATH Keywords

bipartite graphNP-completenessset coverfinite state machinehitting setpartial-matching

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10)

Recommendations

• Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs
• On the complexity of a family of generalized matching problems
• Algorithms and Computation
• On complexity of special maximum matchings constructing
• Simultaneous matchings: Hardness and approximation

Cites work

• scientific article; zbMATH DE number 1194938 (Why is no real title available?)
• Semi-matchings for bipartite graphs and load balancing
• Structure preserving reductions among convex optimization problems

Cited in

(4)

• A Min-Max Theorem for a Constrained Matching Problem
• scientific article; zbMATH DE number 7650074 (Why is no real title available?)
• Approximating the Maximum Sharing Problem
• Equivalence between the minimum covering problem and the maximum matching problem

Describes a project that uses

Uses Software

• Gurobi
• SageMath

This page was built for publication: The minimum maximal k-partial-matching problem

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