Thumbnail - Request a copy

Aspects of upper defensive alliances

Bazgan, Cristina; Fernau, Henning; Tuza, Zsolt (2019), Aspects of upper defensive alliances, Discrete Applied Mathematics, 266, p. 111-120. 10.1016/j.dam.2018.05.061

Type
Article accepté pour publication ou publié
Date
2019
Journal name
Discrete Applied Mathematics
Volume
266
Publisher
Elsevier
Pages
111-120
Publication identifier
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Fernau, Henning
Theoretical Computer Science, University of Trier, Germany
Tuza, Zsolt
Department of Computer Science and Systems Technology [Veszprem]
Abstract (EN)
We consider two notions of minimality in this paper, local and global minimality and we are interested in minimal (strong) defensive alliances of maximum size. We also look at connected versions of these alliances. We show that these problems are NP-hard.
Subjects / Keywords
Defensive alliance; NP-hardness; Approximability; Graphs of bounded average degree