Bounding and approximating minimum maximal matchings in regular graphs

DOI10.1016/J.DISC.2020.112243MaRDI QIDQ2222947zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

edge dominationminimum maximal matching

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

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.

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

Cites work

• A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
• 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
• Approximating edge dominating set in dense graphs
• Approximation hardness of edge dominating set problems
• Computing and Combinatorics
• Edge Dominating Sets in Graphs
• Efficient edge domination in regular graphs
• Improved approximation bounds for edge dominating set in dense graphs
• Integer programming formulations for the minimum weighted maximal matching problem
• Minimum Edge Dominating Sets
• Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs

Cited in

(9)

• scientific article; zbMATH DE number 5799830 (Why is no real title available?)
• Minimum maximal matchings in cubic graphs
• Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
• Hardness and approximation of minimum maximal matchings
• Tight lower bounds on the size of a maximum matching in a regular graph
• Maximal matching and edge domination in complete multipartite graphs
• scientific article; zbMATH DE number 2081000 (Why is no real title available?)
• 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)