Bounding and approximating minimum maximal matchings in regular graphs

Julien Baste; Maximilian Fürst; Michael A. Henning; Elena Mohr; Dieter Rautenbach

doi:10.1016/j.disc.2020.112243

Bounding and approximating minimum maximal matchings in regular graphs

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

Mathematics and Applied Mathematics

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

Abstract

The edge domination number γ_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 γ_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.

Original language	English
Article number	112243
Journal	Discrete Mathematics
Volume	344
Issue number	3
DOIs	https://doi.org/10.1016/j.disc.2020.112243
Publication status	Published - Mar 2021

Keywords

Edge domination
Minimum maximal matching

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2020.112243

Cite this

@article{abc0148960fc4a519a502fa6ed1a7fab,

title = "Bounding and approximating minimum maximal matchings in regular graphs",

abstract = "The edge domination number γ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 γ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.",

keywords = "Edge domination, Minimum maximal matching",

author = "Julien Baste and Maximilian F{\"u}rst and Henning, {Michael A.} and Elena Mohr and Dieter Rautenbach",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier B.V.",

year = "2021",

month = mar,

doi = "10.1016/j.disc.2020.112243",

language = "English",

volume = "344",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Bounding and approximating minimum maximal matchings in regular graphs

AU - Baste, Julien

AU - Fürst, Maximilian

AU - Henning, Michael A.

AU - Mohr, Elena

AU - Rautenbach, Dieter

PY - 2021/3

Y1 - 2021/3

N2 - The edge domination number γ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 γ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.

AB - The edge domination number γ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 γ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.

KW - Edge domination

KW - Minimum maximal matching

UR - http://www.scopus.com/inward/record.url?scp=85097177665&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2020.112243

DO - 10.1016/j.disc.2020.112243

M3 - Article

AN - SCOPUS:85097177665

SN - 0012-365X

VL - 344

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 3

M1 - 112243

ER -

Bounding and approximating minimum maximal matchings in regular graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this