Read full paper at:
http://www.scirp.org/journal/PaperInformation.aspx?PaperID=53574#.VMnXsCzQrzE
Author(s)
Chuan-Min Lee1, Cheng-Chien Lo1, Rui-Xin Ye2, Xun Xu2, Xiao-Han Shi2, Jia-Ying Li2
Affiliation(s)
1Department of Computer and Communication Engineering, Ming Chuan University, The First American University in Asia, Taoyuan, Taiwan, Chinese Taipei.
2Department of Electronic Information Engineering, Fuzhou University, Fuzhou, China.
ABSTRACT
This paper is motivated by the concept of the signed k-domination problem and dedicated to the complexity of the problem on graphs. For any fixed nonnegative integer k, we show that the signed k-domination problem is NP-complete for doubly chordal graphs. For strongly chordal graphs and distance-hereditary graphs, we show that the signed k-domination problem can be solved in polynomial time. We also show that the problem is linear-time solvable 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.
References
http://www.scirp.org/journal/PaperInformation.aspx?PaperID=53574#.VMnXsCzQrzE
Author(s)
Chuan-Min Lee1, Cheng-Chien Lo1, Rui-Xin Ye2, Xun Xu2, Xiao-Han Shi2, Jia-Ying Li2
Affiliation(s)
1Department of Computer and Communication Engineering, Ming Chuan University, The First American University in Asia, Taoyuan, Taiwan, Chinese Taipei.
2Department of Electronic Information Engineering, Fuzhou University, Fuzhou, China.
ABSTRACT
This paper is motivated by the concept of the signed k-domination problem and dedicated to the complexity of the problem on graphs. For any fixed nonnegative integer k, we show that the signed k-domination problem is NP-complete for doubly chordal graphs. For strongly chordal graphs and distance-hereditary graphs, we show that the signed k-domination problem can be solved in polynomial time. We also show that the problem is linear-time solvable 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.
References
| [1] | Wang, C. (2012) The Signed k-Domination Numbers in Graphs. Ars Combinatoria, 106, 205-211. |
| [2] | Hattingh, J.H., Henning, M.A. and Slater, P.J. (1995) The Algorithmic Complexity of Signed Domination in Graphs. Australasian Journal of Combinatorics, 12, 101-112. |
| [3] | Lee, C.-M. and Chang, M.-S. (2008) Variations of Y-Dominating Functions on Graphs. Discrete Mathematics, 308, 4185-4204. http://dx.doi.org/10.1016/j.disc.2007.08.080 |
| [4] | Lee, C.-M. (2014) Remarks on the Complexity of Non-negative Signed Domination. Journal of Networks, 9, 2051- 2058. http://dx.doi.org/10.4304/jnw.9.8.2051-2058 |
| [5] | Brandst?dt, A., Dragan, F.F., Chepoi, V.D. and Voloshin, V. (1998) Dually Chordal Graphs. SIAM Journal on Discrete Mathematics, 11, 437-455. http://dx.doi.org/10.1137/S0895480193253415 |
| [6] | Cai, L., Chen, J., Downey, R.G. and Fellows, M.R. (1997) Advice Classes of Parameterized Tractability. Annals of Pure and Applied Logic, 84, 119-138. http://dx.doi.org/10.1016/S0168-0072(95)00020-8 |
| [7] | Downey, R.G. and Fellows, M.R. (1999) Parameterized Complexity. Monographs in Computer Science, Springer- Verlag. |
| [8] | Moscarini, M. (1993) Doubly Chordal Graphs, Steiner Trees, and Connected Domination. Networks, 23, 59-69. http://dx.doi.org/10.1002/net.3230230108 |
| [9] | Rose, D.J. (1970) Triangulated Graphs and the Elimination Process. Journal of Mathematical Analysis and Applications, 32, 597-609. http://dx.doi.org/10.1016/0022-247X(70)90282-9 |
| [10] | Farber, M. (1983) Characterizations of Strongly Chordal Graphs. Discrete Mathematics, 43, 173-189. http://dx.doi.org/10.1016/0012-365X(83)90154-1 |
| [11] | Paige, R. and Tarjan, R.E. (1987) Three Partition Refinement Algorithms. SIAM Journal on Computing, 16, 973-989. http://dx.doi.org/10.1137/0216062 |
| [12] | Spinrad, J.P. (1993) Doubly Lexical Ordering of Dense 0-1 Matrices. Information Processing Letters, 45, 229-235. http://dx.doi.org/10.1016/0020-0190(93)90209-R |
| [13] | Brandst?dt, A., Le, V.B. and Spinrad, J.P. (1999) Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia 1999. http://dx.doi.org/10.1137/1.9780898719796 |
| [14] | Tarjan, R.E. and Yannakakis, M. (1984) Simple Linear Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. SIAM Joural on Computing, 13, 566-579. http://dx.doi.org/10.1137/0213035 |
| [15] | Booth, S. and Lueker, S. (1976) Testing for the Consecutive Ones Property, Interval Graphs, Graph Planarity Using PQ-Trees Algorithms. Journal of Computer and System Sciences, 13, 335-379. http://dx.doi.org/10.1016/S0022-0000(76)80045-1 |
| [16] | Borie, R.B. and Spinrad, J.P. (1999) Construction of a Simple Elimination Scheme for a Chordal Comparability Graph in Linear Time. Discrete Applied Mathematics, 91, 287-292. http://dx.doi.org/10.1016/S0166-218X(98)00137-1 |
| [17] | Sawada, J. and Spinrad, J.P. (2003) From a Simple Elimination Ordering to a Strong Elimination Ordering in Linear Time. Information Processing Letters, 86, 299-302. http://dx.doi.org/10.1016/S0020-0190(03)00228-X |
| [18] | Chang, M.-S., Hsieh, S.-Y. and Chen, G.-H. (1997) Dynamic Programming on Distance-Hereditary Graphs. Proceedings of the 8th International Symposium o Algorithms and Computation, Lecture Notes in Computer Science, Vol. 1350, 344-353. eww150129lx |
评论
发表评论