Remarks on the Complexity of Signed k-Domination on GraphsReportar como inadecuado




Remarks on the Complexity of Signed k-Domination on Graphs - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

This paper is motivated by the concept ofthe signed k-domination problem and dedicated to the complexity of the problemon graphs. For any fixed nonnegative integer k, we show that the signed k-dominationproblem is NP-complete for doubly chordal graphs. For strongly chordal graphsand distance-hereditary graphs, we show that the signed k-domination problemcan be solved in polynomial time. We also show that the problem is linear-timesolvable for trees, interval graphs, and chordal comparability graphs.

KEYWORDS

Graph Algorithm, Signed k-Domination, Strongly Chordal Graph, Tree, Fixed Parameter Tractable

Cite this paper

Lee, C. , Lo, C. , Ye, R. , Xu, X. , Shi, X. and Li, J. 2015 Remarks on the Complexity of Signed k-Domination on Graphs. Journal of Applied Mathematics and Physics, 3, 32-37. doi: 10.4236-jamp.2015.31005.





Autor: Chuan-Min Lee1, Cheng-Chien Lo1, Rui-Xin Ye2, Xun Xu2, Xiao-Han Shi2, Jia-Ying Li2

Fuente: http://www.scirp.org/



DESCARGAR PDF




Documentos relacionados