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 条

[21] An Upper Bound on the Double Roman Domination Number
Ouldrabah, Lyes
Volkmann, Lutz
BULLETIN OF THE IRANIAN MATHEMATICAL SOCIETY, 2021, 47 (05) : 1315 - 1323
[22] ON EQUALITY IN AN UPPER BOUND FOR THE EQUIVALENCE DOMINATION NUMBER
Arumugam, S.
Sundarakannan, M.
QUAESTIONES MATHEMATICAE, 2015, 38 (01) : 63 - 71
[23] On upper bounds for multiple domination numbers of graphs
Przybylo, Jakub
DISCRETE APPLIED MATHEMATICS, 2013, 161 (16-17) : 2758 - 2763
[24] An upper bound on the double Roman domination number
Amjadi, J.
Nazari-Moghaddam, S.
Sheikholeslami, S. M.
Volkmann, L.
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 36 (01) : 81 - 89
[25] Upper bounds on the k-domination number and the k-Roman domination number
Hansberg, Adriana
Volkmann, Lutz
DISCRETE APPLIED MATHEMATICS, 2009, 157 (07) : 1634 - 1639
[26] Binary programming formulations for the upper domination problem
Burdett, Ryan
Haythorpe, Michael
Newcombe, Alex
MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 2023, 98 (02) : 155 - 168
[27] Domination Parameters in Hypertrees
Jayagopal, R.
Rajasingh, Indra
Rajan, R. Sundara
ALGORITHMS AND DISCRETE APPLIED MATHEMATICS, CALDAM 2016, 2016, 9602 : 299 - 307
[28] Upper and lower bounds on approximating weighted mixed domination
Xiao, Mingyu
THEORETICAL COMPUTER SCIENCE, 2023, 939 : 292 - 302
[29] Upper bounds for domination numbers of the queen's graph
Weakley, WD
DISCRETE MATHEMATICS, 2002, 242 (1-3) : 229 - 243
[30] NORDHAUS-GADDUM BOUNDS FOR UPPER TOTAL DOMINATION
Haynes, Teresa W.
Henning, Michael A.
OPUSCULA MATHEMATICA, 2022, 42 (04) : 573 - 582

← 1 2 3 4 5 →