Bazgan, Cristina and Fernau, Henning and Tuza, Zsolt (2019) Aspects of upper defensive alliances. DISCRETE APPLIED MATHEMATICS, 266. pp. 111-120. ISSN 0166-218X
|
Text
Bazgan-Fernau-Tuza-Aspects_of_Upper_Defensive_Alliances.pdf Download (360kB) | Preview |
Abstract
A defensive alliance in a graph G = (V, E) is a set of vertices S satisfying the condition that every vertex V is an element of S has at least as many neighbors (including itself) in S than it has in V \ S. We also consider strong defensive alliances where the vertex itself is not considered in the inequality. 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. (C) 2018 Elsevier B.V. All rights reserved.
| Item Type: | Article |
|---|---|
| Additional Information: | Funding Agency and Grant Number: National Research, Development and Innovation Office NKFIH [SNN 116095] Funding text: We are grateful to the referee for her/his thorough reading and many comments that have made the paper better readable. Third author's research was supported in part by the National Research, Development and Innovation Office NKFIH under the grant SNN 116095. Université Paris-Dauphine, PSL Research University, CNRS, LAMSADE, Paris, 75016, France Universität Trier, Fachbereich 4, Informatikwissenschaften, Germany Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary Department of Computer Science and Systems Technology, University of Pannonia, Veszprém, Hungary Export Date: 30 October 2019 CODEN: DAMAD Correspondence Address: Tuza, Z.; Alfréd Rényi Institute of Mathematics, Hungarian Academy of SciencesHungary; email: tuza@dcs.uni-pannon.hu Funding details: Office of Research, Innovation and Economic Development, California State Polytechnic University, Pomona Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, SNN 116095 Funding text 1: We are grateful to the referee for her/his thorough reading and many comments that have made the paper better readable. Third author’s research wassupported in part by the National Research, Development and Innovation Office — NKFIH under the grant SNN 116095 . |
| Uncontrolled Keywords: | APPROXIMATION; NP-hardness; Approximability; Defensive alliance; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 16 Jan 2020 12:39 |
| Last Modified: | 16 Jan 2020 12:39 |
| URI: | http://real.mtak.hu/id/eprint/105500 |
Actions (login required)
 |
Edit Item |
