Bounding and approximating minimum maximal matchings in regular graphs
From MaRDI portal
Publication:2222947
DOI10.1016/j.disc.2020.112243zbMath1458.90537arXiv1905.12241OpenAlexW3108836675MaRDI QIDQ2222947
Michael A. Henning, Elena Mohr, Dieter Rautenbach, Maximilian Fürst, Julien Baste
Publication date: 27 January 2021
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1905.12241
Related Items (2)
Minimum maximal matchings in cubic graphs ⋮ Nordhaus-Gaddum-type results on the connected edge domination number
Cites Work
- Approximating edge dominating set in dense graphs
- Efficient edge domination in regular graphs
- Improved approximation bounds for edge dominating set in dense graphs
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- Integer programming formulations for the minimum weighted maximal matching problem
- Approximation hardness of edge dominating set problems
- Minimum Edge Dominating Sets
- Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs
- A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
- Edge Dominating Sets in Graphs
- Computing and Combinatorics
- A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
This page was built for publication: Bounding and approximating minimum maximal matchings in regular graphs
