跳至主要内容

Remarks on the Complexity of Signed k-Domination on Graphs

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
[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
标签：

评论

发表评论

此博客中的热门博文

Electron Spin and Proton Spin in the Hydrogen and Hydrogen-Like Atomic Systems

Read full paper at: http://www.scirp.org/journal/PaperInformation.aspx?PaperID=52202#.VIj7tMnQrzE Author(s) Stanisław Olszewski * Affiliation(s) Institute of Physical Chemistry, Polish Academy of Sciences, Warsaw, Poland . ABSTRACT The mechanical angular momentum and magnetic moment of the electron and proton spin have been calculated semiclassically with the aid of the uncertainty principle for energy and time. The spin effects of both kinds of the elementary particles can be expressed in terms of similar formulae. The quantization of the spin motion has been done on the basis of the old quantum theory. It gives a quantum number n = 1/2 as the index of the spin state acceptable for both the electron and proton
发表评论
阅读全文

Dietary Fiber Content of Waterleaf (Talinum triangulare (Jacq.) Willd) Cultivated with Organic and Conventional Fertilization in Different SeasonsDietary Fiber Content of Waterleaf (Talinum triangulare (Jacq.) Willd) Cultivated with Organic and Conventional Fertilization in Different Seasons

Read  full  paper  at: http://www.scirp.org/journal/PaperInformation.aspx?PaperID=53985#.VN21HizQrzE Author(s)  Nuri Andarwulan 1,2 , Didah Nur Faridah 1,2 , Yolanda Sylvia Prabekti 1 , Harum Fadhilatunnur 1 , Leo Mualim 3 , Sandra Arifin Aziz 3 , Luis Cisneros-Zevallos 4   Affiliation(s) 1 Department of Food Science and Technology, Bogor Agricultural University, Bogor, Indonesia . 2 Southeast Asian Food and Agricultural Science and Technology (SEAFAST) Center, Bogor Agricultural University, Bogor, Indonesia . 3 Department of Agronomy and Horticulture, Bogor Agricultural University, Bogor, Indonesia . 4 Department of Horticultural Sciences, Texas A&M University, College Station, USA . ABSTRACT Waterleaf ( Talinum triangulare (Jacq.) Willd has long been eaten in Indonesia as vegetable and the main parts consumed are leaves and young shoots. Waterleaf is sticky presumably due to its pectin content which is associated to dietary fiber. The dietary fiber which
发表评论
阅读全文