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 条
  • [1] Upper Domination: Complexity and Approximation
    Bazgan, Cristina
    Brankovic, Ljiljana
    Casel, Katrin
    Fernau, Henning
    Jansen, Klaus
    Klein, Kim-Manuel
    Lampis, Michael
    Liedloff, Mathieu
    Monnot, Jerome
    Paschos, Vangelis Th.
    COMBINATORIAL ALGORITHMS, 2016, 9843 : 241 - 252
  • [2] A Boundary Property for Upper Domination
    AbouEisha, Hassan
    Hussain, Shahid
    Lozin, Vadim
    Monnot, Jerome
    Ries, Bernard
    Zamaraev, Viktor
    Combinatorial Algorithms, 2016, 9843 : 229 - 240
  • [3] A Dichotomy for Upper Domination in Monogenic Classes
    AbouEisha, Hassan
    Hussain, Shahid
    Lozin, Vadim
    Monnot, Jerome
    Ries, Bernard
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS (COCOA 2014), 2014, 8881 : 258 - 267
  • [4] Algorithmic aspects of upper edge domination
    Monnot, Jerome
    Fernau, Henning
    Manlove, David
    THEORETICAL COMPUTER SCIENCE, 2021, 877 : 46 - 57
  • [5] On upper bounds for the independent transversal domination number
    Brause, Christoph
    Henning, Michael A.
    Ozeki, Kenta
    Schiermeyer, Ingo
    Vumar, Elkin
    DISCRETE APPLIED MATHEMATICS, 2018, 236 : 66 - 72
  • [6] Algorithmic Aspects of Upper Domination: A Parameterised Perspective
    Bazgan, Cristina
    Brankovic, Ljiljana
    Casel, Katrin
    Fernau, Henning
    Jansen, Klaus
    Klein, Kim-Manuel
    Lampis, Michael
    Liedloff, Mathieu
    Monnot, Jerome
    Paschos, Vangelis Th.
    ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, 2016, 9778 : 113 - 124
  • [7] On the Complexity Landscape of the Domination Chain
    Bazgan, Cristina
    Brankovic, Ljiljana
    Casel, Katrin
    Fernau, Henning
    ALGORITHMS AND DISCRETE APPLIED MATHEMATICS, CALDAM 2016, 2016, 9602 : 61 - 72
  • [8] Many Facets of Dualities
    Nesetril, Jaroslav
    RESEARCH TRENDS IN COMBINATORIAL OPTIMIZATION, 2009, : 285 - 302
  • [9] Essential upper bounds on the total domination number
    Henning, Michael A.
    DISCRETE APPLIED MATHEMATICS, 2018, 244 : 103 - 115
  • [10] General upper bound on the game domination number
    Bujtas, Csilla
    DISCRETE APPLIED MATHEMATICS, 2020, 285 : 530 - 538
12345