Hardness and approximation of minimum maximal matchings
DOI10.1080/00207160.2013.853052zbMath1305.05188OpenAlexW1988896516MaRDI QIDQ2935383
Tınaz Ekim, Marc Demange, Cerasela Tanasescu
Publication date: 29 December 2014
Published in: International Journal of Computer Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/00207160.2013.853052
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) 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) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Cites Work
- Edge domination on bipartite permutation graphs and cotriangulated graphs
- Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
- Approximating edge dominating set in dense graphs
- Improved approximation bounds for edge dominating set in dense graphs
- Minimum-maximal matching in series-parallel graphs
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem
- Approximation hardness of edge dominating set problems
- Minimum Edge Dominating Sets
- A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
- Edge Dominating Sets in Graphs
- An Analysis of the Greedy Heuristic for Independence Systems
- Randomly matchable graphs
- Approximation algorithms for NP-complete problems on planar graphs
- The edge domination problem
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
