A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem

DOI10.1007/978-3-540-93980-1_21zbMath1209.68640OpenAlexW2260202313MaRDI QIDQ3602847

Elad Rainshmidt, Zvi Gotthilf, Moshe Lewenstein

Publication date: 12 February 2009

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-93980-1_21

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (8)

Hardness and approximation of minimum maximal matchings ⋮ Domination versus edge domination ⋮ An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem ⋮ Bounding and approximating minimum maximal matchings in regular graphs ⋮ Approximating Edge Dominating Set in Dense Graphs ⋮ Decomposition algorithms for solving the minimum weight maximal matching problem ⋮ Approximating edge dominating set in dense graphs ⋮ Tight inapproximability of minimum maximal matching on bipartite graphs and related problems

Cites Work

• Unnamed Item
• Unnamed Item
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• Approximation hardness of edge dominating set problems
• Minimum Edge Dominating Sets
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• Edge Dominating Sets in Graphs
• Approximation algorithms for NP-complete problems on planar graphs
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Improved Approximation Bounds for Edge Dominating Set in Dense Graphs
• A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem

This page was built for publication: A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem