Integer programming formulations for the minimum weighted maximal matching problem

DOI10.1007/s11590-011-0351-xzbMath1254.90130OpenAlexW2075081186MaRDI QIDQ1758060

Z. Caner Taşkın, Tınaz Ekim

Publication date: 7 November 2012

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-011-0351-x

zbMATH Keywords

integer programmingedge dominating setminimum maximal matching

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Mixed integer programming (90C11) Matching models (91B68)

Related Items (7)

Modelling and solving the perfect edge domination problem ⋮ Facility location problems on graphs with non-convex neighborhoods ⋮ Domination versus edge domination ⋮ Bounding and approximating minimum maximal matchings in regular graphs ⋮ Decomposition algorithms for solving the minimum weight maximal matching problem ⋮ Maximal matching polytope in trees ⋮ Minimum cost \(b\)-matching problems with neighborhoods

Cites Work

• Unnamed Item
• Unnamed Item
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• Improved approximation bounds for edge dominating set in dense graphs
• Minimum-maximal matching in series-parallel graphs
• A global optimization method for minimum maximal flow problem
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• Approximation hardness of edge dominating set problems
• Approximability of the capacitated \(b\)-edge dominating set problem
• Improving Discrete Model Representations via Symmetry Considerations
• Minimum Edge Dominating Sets
• Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs
• Edge Dominating Sets in Graphs
• The edge domination problem
• Paths, Trees, and Flowers
• Computing and Combinatorics

This page was built for publication: Integer programming formulations for the minimum weighted maximal matching problem