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

DOI10.1007/978-3-540-93980-1_21MaRDI QIDQ3602847zbMATH OpenOpenAlexFDO

Authors Zvi Gotthilf, Elad Rainshmidt, 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

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

Recommendations

• Hardness and approximation of minimum maximal matchings
• Tight approximation ratio for Minimum Maximal Matching
• An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem
• Computing and Combinatorics
• Algorithms – ESA 2004

Cites work

• scientific article; zbMATH DE number 3869066 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation hardness of edge dominating set problems
• Edge Dominating Sets in Graphs
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• Improved Approximation Bounds for Edge Dominating Set in Dense Graphs
• Minimum Edge Dominating Sets
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs

Cited in

(18)

• An 0(n log n) algorithm for the convex bipartite matching problem
• A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem
• Hardness and approximation of minimum maximal matchings
• Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
• A \(\frac{1}{2}\)-integral relaxation for the \(A\)-matching problem
• Integer programming formulations for the minimum weighted maximal matching problem
• Bounding and approximating minimum maximal matchings in regular graphs
• Tight approximation ratio for Minimum Maximal Matching
• A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem
• An \(O(mn^ 2)\) algorithm for the maximin problem in \(E^ 2\)
• A general class of heuristics for minimum weight perfect matching and fast special cases with doubly and triply logarithmic errors
• Decomposition algorithms for solving the minimum weight maximal matching problem
• Approximating edge dominating set in dense graphs
• Computing and Combinatorics
• An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem
• Approximating edge dominating set in dense graphs
• scientific article; zbMATH DE number 1003276 (Why is no real title available?)
• Domination versus edge domination

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

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