Algorithmic aspects of the k-domination problem in graphs

被引：18
|
作者：
Lan, James K. [1 ]
Chang, Gerard Jennhwa [1 ,2 ,3 ]
机构：
[1] Natl Taiwan Univ, Dept Math, Taipei 10617, Taiwan
[2] Natl Taiwan Univ, Taida Inst Math Sci, Taipei 10617, Taiwan
[3] Natl Ctr Theoret Sci, Taipei Off, Taipei, Taiwan
来源：
DISCRETE APPLIED MATHEMATICS | 2013年 / 161卷 / 10-11期
关键词：
k-domination; Tree; Block graph; Cactus; Block-cactus graph; Split graph; Algorithm; NP-complete; NUMBER;
D O I：
10.1016/j.dam.2013.01.015
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
For a positive integer k, a k-dominating set of a graph G is a subset D subset of V (G) such that every vertex not in D is adjacent to at least k vertices in D. The k-domination problem is to determine a minimum k-dominating set of G. This paper studies the k-domination problem in graphs from an algorithmic point of view. In particular, we present a linear-time algorithm for the k-domination problem for graphs in which each block is a clique, a cycle or a complete bipartite graph. This class of graphs includes trees, block graphs, cacti and block-cactus graphs. We also establish NP-completeness of the k-domination problem in split graphs. (C) 2013 Elsevier B.V. All rights reserved.
引用
收藏
页码：1513 / 1520
页数：8
相关论文
共 50 条
  • [31] Algorithmic aspect of k-tuple domination in graphs
    Liao, CS
    Chang, GJ
    TAIWANESE JOURNAL OF MATHEMATICS, 2002, 6 (03): : 415 - 420
  • [32] Algorithmic Aspects of Some Variants of Domination in Graphs
    Kumar, J. Pavan
    Reddy, P. Venkata Subba
    ANALELE STIINTIFICE ALE UNIVERSITATII OVIDIUS CONSTANTA-SERIA MATEMATICA, 2020, 28 (03): : 153 - 170
  • [33] Algorithmic aspects of Roman {3}-domination in graphs
    Chakradhar, Padamutham
    Reddy, Palagiri Venkata Subba
    RAIRO-OPERATIONS RESEARCH, 2022, 56 (04) : 2277 - 2291
  • [34] Algorithmic aspects of paired disjunctive domination in graphs
    Henning, Michael A.
    Pandey, Arti
    Tripathi, Vikash
    THEORETICAL COMPUTER SCIENCE, 2023, 966
  • [35] On the mixed domination problem in graphs
    Lan, James K.
    Chang, Gerard Jennhwa
    THEORETICAL COMPUTER SCIENCE, 2013, 476 : 84 - 93
  • [36] Variable neighborhood search for solving the k-domination problem
    Predojevic, Milan
    Kartelj, Aleksandar
    Djukanovic, Marko
    PROCEEDINGS OF THE 2023 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE COMPANION, GECCO 2023 COMPANION, 2023, : 239 - 242
  • [37] Algorithmic aspects of secure domination in unit disk graphs
    Wang, Cai-Xia
    Yang, Yu
    Xu, Shou-Jun
    INFORMATION AND COMPUTATION, 2023, 295
  • [38] Algorithmic aspects of upper paired-domination in graphs
    Henning, Michael A.
    Pradhan, D.
    THEORETICAL COMPUTER SCIENCE, 2020, 804 : 98 - 114
  • [39] Algorithmic aspects of total Roman {3}-domination in graphs
    Chakradhar, Padamutham
    Reddy, Palagiri Venkata Subba
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2021, 13 (05)
  • [40] Algorithmic aspects of outer independent Roman domination in graphs
    Sharma, Amit
    Kumar, Jakkepalli Pavan
    Subba Reddy, P. Venkata
    Arumugam, S.
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2022, 14 (05)
12345