Geodesic
On Minimum Maximal Distance-k Matchings
Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1 Cet article a éte moissonné depuis la source Episciences

Voir la notice de l'article

We study the computational complexity of several problems connected with finding a maximal distance-$k$ matching of minimum cardinality or minimum weight in a given graph. We introduce the class of $k$-equimatchable graphs which is an edge analogue of $k$-equipackable graphs. We prove that the recognition of $k$-equimatchable graphs is co-NP-complete for any fixed $k \ge 2$. We provide a simple characterization for the class of strongly chordal graphs with equal $k$-packing and $k$-domination numbers. We also prove that for any fixed integer $\ell \ge 1$ the problem of finding a minimum weight maximal distance-$2\ell$ matching and the problem of finding a minimum weight $(2 \ell - 1)$-independent dominating set cannot be approximated in polynomial time in chordal graphs within a factor of $\delta \ln |V(G)|$ unless $\mathrm{P} = \mathrm{NP}$, where $\delta$ is a fixed constant (thereby improving the NP-hardness result of Chang for the independent domination case). Finally, we show the NP-hardness of the minimum maximal induced matching and independent dominating set problems in large-girth planar graphs. 
@article{DMTCS_2018_20_1_a2,
     author = {Kartynnik, Yury and Ryzhikov, Andrew},
     title = {On {Minimum} {Maximal} {Distance-k} {Matchings}},
     journal = {Discrete mathematics & theoretical computer science},
     year = {2018},
     volume = {20},
     number = {1},
     doi = {10.23638/DMTCS-20-1-3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-3/}
}
TY  - JOUR
AU  - Kartynnik, Yury
AU  - Ryzhikov, Andrew
TI  - On Minimum Maximal Distance-k Matchings
JO  - Discrete mathematics & theoretical computer science
PY  - 2018
VL  - 20
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-3/
DO  - 10.23638/DMTCS-20-1-3
LA  - en
ID  - DMTCS_2018_20_1_a2
ER  - 
%0 Journal Article
%A Kartynnik, Yury
%A Ryzhikov, Andrew
%T On Minimum Maximal Distance-k Matchings
%J Discrete mathematics & theoretical computer science
%D 2018
%V 20
%N 1
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-3/
%R 10.23638/DMTCS-20-1-3
%G en
%F DMTCS_2018_20_1_a2
Kartynnik, Yury; Ryzhikov, Andrew. On Minimum Maximal Distance-k Matchings. Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1. doi: 10.23638/DMTCS-20-1-3

Cité par Sources :