The many facets of upper domination

被引：26
作者：
Bazgan, Cristina [1 ,6 ]
Brankovic, Ljiljana [3 ]
Casel, Katrin [2 ]
Fernau, Henning [2 ]
Jansen, Klaus [5 ]
Klein, Kim-Manuel [5 ]
Lampis, Michael [1 ]
Liedloff, Mathieu [4 ]
Monnot, Jerome [1 ]
Paschos, Vangelis Th. [1 ]
机构：
[1] Univ Paris 09, PSL Res Univ, CNRS, LAMSADE, F-75016 Paris, France
[2] Univ Trier, Fachbereich 4, Abt Informat, D-54286 Trier, Germany
[3] Univ Newcastle, Sch Elect Engn & Comp Sci, Callaghan, NSW 2308, Australia
[4] Univ Orleans, INSA, Ctr Val de Loire, LIFO EA 4022, F-45067 Orleans, France
[5] Univ Kiel, Inst Informat, D-24098 Kiel, Germany
[6] Inst Univ France, Paris, France
来源：
THEORETICAL COMPUTER SCIENCE | 2018年 / 717卷
关键词：
Dominating set; (In)approximability; Fixed parameter (in)tractability; Extension problems; Bounded-degree graphs; COMPUTATIONAL-COMPLEXITY; FAST ALGORITHMS; UPPER-BOUNDS; GRAPHS; APPROXIMATION; IRREDUNDANCE; SETS; INDEPENDENCE; OPTIMIZATION; CLIQUE;
D O I：
10.1016/j.tcs.2017.05.042
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
This paper studies UPPER DOMINATION, i.e., the problem of computing the maximum cardinality of a minimal dominating set in a graph with respect to classical and parameterised complexity as well as approximability. (C) 2017 Elsevier B.V. All rights reserved.
引用
收藏
页码：2 / 25
页数：24
相关论文
共 50 条
  • [31] Upper Bounds for the Paired-Domination Numbers of Graphs
    Lu, Changhong
    Wang, Chao
    Wang, Kan
    GRAPHS AND COMBINATORICS, 2016, 32 (04) : 1489 - 1494
  • [32] Upper Bounds for the Paired-Domination Numbers of Graphs
    Changhong Lu
    Chao Wang
    Kan Wang
    Graphs and Combinatorics, 2016, 32 : 1489 - 1494
  • [33] Upper and Lower Bounds on Approximating Weighted Mixed Domination
    Xiao, Mingyu
    COMPUTING AND COMBINATORICS, COCOON 2019, 2019, 11653 : 554 - 566
  • [34] An upper bound on the total restrained domination number of a tree
    Hattingh, Johannes H.
    Jonck, Elizabeth
    Joubert, Ernst J.
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2010, 20 (03) : 205 - 223
  • [35] More on independent transversal domination
    Pushpam, P. Roushini Leely
    Bhanthavi, K. Priya
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2024, 16 (07)
  • [36] Progressive Algorithms for Domination and Independence
    Fabianski, Grzegorz
    Pilipczuk, Michal
    Siebertz, Sebastian
    Torunczyk, Szymon
    36TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2019), 2019,
  • [37] Towards a new framework for domination
    Caceres, Jose
    Marquez, Alberto
    Morales, Maria
    Luz Puertas, Maria
    COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2011, 62 (01) : 44 - 50
  • [38] The domination number of plane triangulations
    Spacapan, Simon
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2020, 143 : 42 - 64
  • [39] Can International Organizations Turn 'Rogue'? The Many Facets of Institutional Capture
    Schmalenbach, Kirsten
    INTERNATIONAL ORGANIZATIONS LAW REVIEW, 2024, 21 (03) : 446 - 453
  • [40] DOMINATION, ETERNAL DOMINATION AND CLIQUE COVERING
    Klostermeyer, William F.
    Mynhardt, C. M.
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2015, 35 (02) : 283 - 300
12345