Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs

DOI10.1007/978-3-540-79228-4_32zbMath1139.05337OpenAlexW1502057009MaRDI QIDQ3502661

Tınaz Ekim, Marc Demange

Publication date: 27 May 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-79228-4_32

zbMATH Keywords

regular bipartite graphsstable marriageMinimum Maximal Matchingunmatched pairs

Mathematics Subject Classification ID

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)

Related Items (9)

Minimum maximal matchings in cubic graphs ⋮ Modelling and solving the perfect edge domination problem ⋮ Smallest maximal matchings of graphs ⋮ Bounding and approximating minimum maximal matchings in regular graphs ⋮ Integer programming formulations for the minimum weighted maximal matching problem ⋮ Improved approximation bounds for edge dominating set in dense graphs ⋮ Decomposition algorithms for solving the minimum weight maximal matching problem ⋮ Maximal matching polytope in trees ⋮ Approximating edge dominating set in dense graphs

Cites Work

• Unnamed Item
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• A tale of two mechanisms: Student placement
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• Current trends in economics. Theory and applications. Proceedings of the 3rd international meeting held in Antalya, Turkey, June 1997
• Minimum Edge Dominating Sets
• Edge Dominating Sets in Graphs
• The edge domination problem
• College Admissions and the Stability of Marriage

This page was built for publication: Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs