A (2 - c \frac{\log {n}}{n}) Approximation Algorithm for the Minimum Maximal Matching Problem
DOI10.1007/978-3-540-93980-1_21zbMATH Open1209.68640OpenAlexW2260202313MaRDI QIDQ3602847FDOQ3602847
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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- Approximation algorithms for NP-complete problems on planar graphs
- Title not available (Why is that?)
- Edge Dominating Sets in Graphs
- Minimum Edge Dominating Sets
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- 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
- Edge domination on bipartite permutation graphs and cotriangulated graphs
- Approximation hardness of edge dominating set problems
- Improved Approximation Bounds for Edge Dominating Set in Dense 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\)
- Decomposition algorithms for solving the minimum weight maximal matching problem
- A general class of heuristics for minimum weight perfect matching and fast special cases with doubly and triply logarithmic errors
- Computing and Combinatorics
- Approximating edge dominating set in dense graphs
- An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem
- Approximating edge dominating set in dense graphs
- Title not available (Why is that?)
- 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)
