Bounding and approximating minimum maximal matchings in regular graphs

DOI10.1016/J.DISC.2020.112243zbMATH Open1458.90537arXiv1905.12241OpenAlexW3108836675MaRDI QIDQ2222947FDOQ2222947

Authors: Julien Baste, Maximilian Fürst, Michael A. Henning, Elena Mohr, Dieter Rautenbach 

Publication date: 27 January 2021

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: The edge domination number $gamm{a}_e(G)$ of a graph $G$ is the minimum size of a maximal matching in $G$. It is well known that this parameter is computationally very hard, and several approximation algorithms and heuristics have been studied. In the present paper, we provide best possible upper bounds on $gamm{a}_e(G)$ for regular and non-regular graphs $G$ in terms of their order and maximum degree. Furthermore, we discuss algorithmic consequences of our results and their constructive proofs.

Full work available at URL: https://arxiv.org/abs/1905.12241

Recommendations

• Algorithms and Computation
• Small edge dominating sets of regular graphs
• Hardness and approximation of minimum maximal matchings
• Algorithmic aspects of upper edge domination
• On total domination and minimum maximal matchings in graphs

zbMATH Keywords

edge dominationminimum maximal matching

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Edge Dominating Sets in Graphs
• Minimum Edge Dominating Sets
• 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
• A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
• Computing and Combinatorics
• Approximation hardness of edge dominating set problems
• 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
• Approximating edge dominating set in dense graphs
• Integer programming formulations for the minimum weighted maximal matching problem

Cited In (9)

• Title not available (Why is that?)
• Minimum maximal matchings in cubic graphs
• Hardness and approximation of minimum maximal matchings
• Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
• Tight lower bounds on the size of a maximum matching in a regular graph
• Maximal matching and edge domination in complete multipartite graphs
• Title not available (Why is that?)
• Nordhaus-Gaddum-type results on the connected edge domination number
• Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width

This page was built for publication: Bounding and approximating minimum maximal matchings in regular graphs

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