On the complexity of signed and minus total domination in graphs

被引：9
|
作者：
Lee, Chuan-Min
机构：
[1] Department of Computer and Communication Engineering, Ming Chuan University, Guishan District, Taoyuan County 333
来源：
INFORMATION PROCESSING LETTERS | 2009年 / 109卷 / 20期
关键词：
Graph algorithms; Minus total dominating functions; Signed total dominating functions; Chordal bipartite graphs; Doubly chordal graphs; NUMBER;
D O I：
10.1016/j.ipl.2009.08.002
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In this paper we present unified methods to solve the minus and signed total domination problems for chordal bipartite graphs and trees in O(n(2)) and O(n + m) time, respectively. We also prove that the decision problem for the signed total domination problem on doubly chordal graphs is NP-complete. Note that bipartite permutation graphs, biconvex bipartite graphs, and convex bipartite graphs are subclasses of chordal bipartite graphs. (c) 2009 Elsevier B.V. All rights reserved.
引用
收藏
页码：1177 / 1181
页数：5
相关论文
共 50 条
  • [1] On the Complexity of Reverse Minus and Signed Domination on Graphs
    Lee, Chuan-Min
    Lo, Cheng-Chien
    JOURNAL OF INTERCONNECTION NETWORKS, 2015, 15 (1-2)
  • [2] Remarks on the minus (signed) total domination in graphs
    Shan, Erfang
    Cheng, T. C. E.
    DISCRETE MATHEMATICS, 2008, 308 (15) : 3373 - 3380
  • [3] Signed and minus total domination on subclasses of bipartite graphs
    Lee, Chuan-Min
    ARS COMBINATORIA, 2011, 100 : 129 - 149
  • [4] Efficient minus and signed domination in graphs
    Lu, CL
    Peng, SL
    Tang, CY
    ALGORITHM AND COMPUTATION, PROCEEDINGS, 2001, 1969 : 241 - 253
  • [5] Signed and minus domination in bipartite graphs
    Bohdan Zelinka
    Czechoslovak Mathematical Journal, 2006, 56 : 587 - 590
  • [6] Efficient minus and signed domination in graphs
    Lu, CL
    Peng, SL
    Tang, CY
    THEORETICAL COMPUTER SCIENCE, 2003, 301 (1-3) : 381 - 397
  • [7] Signed and minus domination in bipartite graphs
    Zelinka, Bohdan
    CZECHOSLOVAK MATHEMATICAL JOURNAL, 2006, 56 (02) : 587 - 590
  • [8] Signed and Minus Domination in Complete Multipartite Graphs
    Liang, Hongyu
    ARS COMBINATORIA, 2016, 126 : 133 - 142
  • [9] Minus total domination in graphs
    Hua-Ming Xing
    Hai-Long Liu
    Czechoslovak Mathematical Journal, 2009, 59 : 861 - 870
  • [10] Minus total domination in graphs
    Xing, Hua-Ming
    Liu, Hai-Long
    CZECHOSLOVAK MATHEMATICAL JOURNAL, 2009, 59 (04) : 861 - 870
12345