Some complexity results on semipaired domination in graphs

التفاصيل البيبلوغرافية
العنوان:	Some complexity results on semipaired domination in graphs
المؤلفون:	Vikash Tripathi, Kusum, Arti Pandey
المصدر:	AKCE International Journal of Graphs and Combinatorics, Pp 1-7 (2024)
بيانات النشر:	Taylor & Francis Group, 2024.
سنة النشر:	2024
المجموعة:	LCC:Mathematics
مصطلحات موضوعية:	Semipaired domination, AT-free graphs, planar graphs, NP-completeness, approximation algorithm, Mathematics, QA1-939
الوصف:	Let [Formula: see text] be a graph without any isolated vertices. A semipaired dominating set [Formula: see text] of G, is a dominating set of G, if D can be partitioned into cardinality 2 subsets such that the vertices in each of these subsets are at distance at most two from each other. The Min-Semi-PD problem is to compute a minimum cardinality semipaired dominating set of a given graph G. It is known that the decision version of the problem is NP-complete for bipartite graphs and split graphs. In this article, we resolve the complexity of the problem in two well studied graph classes, namely, AT-free graphs and planar graphs. We show that the decision version of the Min-Semi-PD problem remains NP-complete for planar graphs. On the positive side, we propose a polynomial-time exact algorithm for the Min-Semi-PD problem in AT-free graphs, but the complexity of the algorithm is quite high. So, in addition, we also give a linear-time constant factor approximation algorithm for the problem in AT-free graphs.
نوع الوثيقة:	article
وصف الملف:	electronic resource
اللغة:	English
تدمد:	09728600 2543-3474 0972-8600
Relation:	https://doaj.org/toc/0972-8600; https://doaj.org/toc/2543-3474
DOI:	10.1080/09728600.2024.2443910
URL الوصول:	https://doaj.org/article/ce88e7a6aea34dd6ae62d47706dbbe87
رقم الانضمام:	edsdoj.88e7a6aea34dd6ae62d47706dbbe87
قاعدة البيانات:	Directory of Open Access Journals

View record in DOAJ

الوصف
تدمد:	09728600 25433474
DOI:	10.1080/09728600.2024.2443910