Algorithmic aspects of k-tuple total domination in graphs
Data(s) |
2012
|
---|---|
Resumo |
For a fixed positive integer k, a k-tuple total dominating set of a graph G = (V. E) is a subset T D-k of V such that every vertex in V is adjacent to at least k vertices of T Dk. In minimum k-tuple total dominating set problem (MIN k-TUPLE TOTAL DOM SET), it is required to find a k-tuple total dominating set of minimum cardinality and DECIDE MIN k-TUPLE TOTAL DOM SET is the decision version of MIN k-TUPLE TOTAL DOM SET problem. In this paper, we show that DECIDE MIN k-TUPLE TOTAL DOM SET is NP-complete for split graphs, doubly chordal graphs and bipartite graphs. For chordal bipartite graphs, we show that MIN k-TUPLE TOTAL DOM SET can be solved in polynomial time. We also propose some hardness results and approximation algorithms for MIN k-TUPLE TOTAL DOM SET problem. (c) 2012 Elsevier B.V. All rights reserved. |
Formato |
application/pdf |
Identificador |
http://eprints.iisc.ernet.in/45336/1/inf_pro_let_112-21_816_2012.pdf Pradhan, D (2012) Algorithmic aspects of k-tuple total domination in graphs. In: INFORMATION PROCESSING LETTERS, 112 (21). pp. 816-822. |
Publicador |
ELSEVIER SCIENCE BV |
Relação |
http://dx.doi.org/10.1016/j.ipl.2012.07.010 http://eprints.iisc.ernet.in/45336/ |
Palavras-Chave | #Computer Science & Automation (Formerly, School of Automation) |
Tipo |
Journal Article PeerReviewed |