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 条

[41] Extremal graphs for a new upper bound on domination parameters in graphs
Blidia, Mostafa
Chellali, Mustapha
Maffray, Frederic
[J]. DISCRETE MATHEMATICS, 2006, 306 (19-20) : 2314 - 2326
[42] The 4/5 upper bound on the game total domination number
Henning, Michael A.
Klavzar, Sandi
Rall, Douglas F.
[J]. COMBINATORICA, 2017, 37 (02) : 223 - 251
[43] An upper bound for domination number of 5-regular graphs
Hua-Ming Xing
Liang Sun
Xue-Gang Chen
[J]. Czechoslovak Mathematical Journal, 2006, 56 : 1049 - 1061
[44] On the complexity of variations of mixed domination on graphs
Lee, Chuan-Min
[J]. INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2016, 93 (11) : 1937 - 1963
[45] An upper bound for domination number of 5-regular graphs
Xing, Hua-Ming
Sun, Liang
Chen, Xue-Gang
[J]. CZECHOSLOVAK MATHEMATICAL JOURNAL, 2006, 56 (03) : 1049 - 1061
[46] On a Conjecture about Inverse Domination in Graphs
Frendrup, Allan
Henning, Michael A.
Randerath, Bert
Vestergaard, Preben Dahl
[J]. ARS COMBINATORIA, 2010, 97A : 129 - 143
[47] THE COMPARED COSTS OF DOMINATION LOCATION-DOMINATION AND IDENTIFICATION
Hudry, Olivier
Lobstein, Antoine
[J]. DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2020, 40 (01) : 127 - 147
[48] Gallai-type theorems and domination parameters
Domke, GS
Dunbar, JE
Markus, LR
[J]. DISCRETE MATHEMATICS, 1997, 167 : 237 - 248
[49] An upper bound on the 2-outer-independent domination number of a tree
Krzywkowski, Marcin
[J]. COMPTES RENDUS MATHEMATIQUE, 2011, 349 (21-22) : 1123 - 1125
[50] Total Positive Influence Domination on Weighted Networks
Greetham, Danica Vukadinovic
Charlton, Nathaniel
Poghosyan, Anush
[J]. COMPLEX NETWORKS AND THEIR APPLICATIONS VIII, VOL 1, 2020, 881 : 325 - 336

← 1 2 3 4 5 →