ProV Logo
0
On Minimum Maximal Distance-k Matchings
Kartynnik, Yury...

Free

On Minimum Maximal Distance-k Matchings by Kartynnik, Yury ( Author )
Lemonjar Open Access
N.A
15-02-2016
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≥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 ℓ≥1 the problem of finding a minimum weight maximal distance-2ℓ matching and the problem of finding a minimum weight (2ℓ−1)-independent dominating set cannot be approximated in polynomial time in chordal graphs within a factor of δln|V(G)| unless P=NP, where δ 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
pdf
36.88 KB
English
-
MYR 0.01
-
https://arxiv.org/abs/1602.04581
Share this eBook