Domination Chain: Characterisation, Classical Complexity, Parameterised Complexity and Approximability

Cristina Bazgan; Ljiljana Brankovic; Katrin Casel; Henning Fernau

doi:10.1016/j.dam.2019.10.005

Domination Chain: Characterisation, Classical Complexity, Parameterised Complexity and Approximability

Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau

Computer Science

Research output: Contribution to journal › Conference article › peer-review

8 Citations (Scopus)

Abstract

We survey the most important results regarding the domination chain parameters, including the characterisation of the domination sequence, complexity of exact and parameterised algorithms, and approximation and inapproximability ratios. We provide a number of new results for the upper and lower irredundance and their complements, and a few results for other domination chain problems. In particular, we analyse the structure of maximum irredundant sets and we provide new bounds on the upper irredundance number. We show several approximability results for upper and lower irredundance and their complements on general graphs; all four problems remain NP-hard even on planar cubic graphs and APX-hard on cubic graphs. Finally, we give some results on everywhere dense graphs, and study some related extension problems.

Original language	English
Pages (from-to)	23-42
Journal	Discrete Applied Mathematics
Volume	280
Early online date	14 Oct 2019
DOIs	https://doi.org/10.1016/j.dam.2019.10.005
Publication status	Published - 15 Jun 2020
Event	CALDAM 2016: Conference on Algorithms and Discrete Applied Mathematics - University of Kerala, Thiruvanthapuram, India Duration: 18 Feb 2016 → 20 Feb 2016

Access to Document

10.1016/j.dam.2019.10.005

https://hdl.handle.net/1959.11/53636

Handle.net

Persistent link

Cite this

@article{a45a8419208847e8985b16442e68995d,

title = "Domination Chain: Characterisation, Classical Complexity, Parameterised Complexity and Approximability",

abstract = "We survey the most important results regarding the domination chain parameters, including the characterisation of the domination sequence, complexity of exact and parameterised algorithms, and approximation and inapproximability ratios. We provide a number of new results for the upper and lower irredundance and their complements, and a few results for other domination chain problems. In particular, we analyse the structure of maximum irredundant sets and we provide new bounds on the upper irredundance number. We show several approximability results for upper and lower irredundance and their complements on general graphs; all four problems remain NP-hard even on planar cubic graphs and APX-hard on cubic graphs. Finally, we give some results on everywhere dense graphs, and study some related extension problems.",

author = "Cristina Bazgan and Ljiljana Brankovic and Katrin Casel and Henning Fernau",

year = "2020",

month = jun,

day = "15",

doi = "10.1016/j.dam.2019.10.005",

language = "English",

volume = "280",

pages = "23--42",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier BV, North-Holland",

note = "CALDAM 2016: Conference on Algorithms and Discrete Applied Mathematics ; Conference date: 18-02-2016 Through 20-02-2016",

}

TY - JOUR

T1 - Domination Chain

T2 - CALDAM 2016: Conference on Algorithms and Discrete Applied Mathematics

AU - Bazgan, Cristina

AU - Brankovic, Ljiljana

AU - Casel, Katrin

AU - Fernau, Henning

PY - 2020/6/15

Y1 - 2020/6/15

N2 - We survey the most important results regarding the domination chain parameters, including the characterisation of the domination sequence, complexity of exact and parameterised algorithms, and approximation and inapproximability ratios. We provide a number of new results for the upper and lower irredundance and their complements, and a few results for other domination chain problems. In particular, we analyse the structure of maximum irredundant sets and we provide new bounds on the upper irredundance number. We show several approximability results for upper and lower irredundance and their complements on general graphs; all four problems remain NP-hard even on planar cubic graphs and APX-hard on cubic graphs. Finally, we give some results on everywhere dense graphs, and study some related extension problems.

AB - We survey the most important results regarding the domination chain parameters, including the characterisation of the domination sequence, complexity of exact and parameterised algorithms, and approximation and inapproximability ratios. We provide a number of new results for the upper and lower irredundance and their complements, and a few results for other domination chain problems. In particular, we analyse the structure of maximum irredundant sets and we provide new bounds on the upper irredundance number. We show several approximability results for upper and lower irredundance and their complements on general graphs; all four problems remain NP-hard even on planar cubic graphs and APX-hard on cubic graphs. Finally, we give some results on everywhere dense graphs, and study some related extension problems.

UR - https://www.scopus.com/pages/publications/85073509299

U2 - 10.1016/j.dam.2019.10.005

DO - 10.1016/j.dam.2019.10.005

M3 - Conference article

SN - 0166-218X

VL - 280

SP - 23

EP - 42

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

Y2 - 18 February 2016 through 20 February 2016

ER -

Domination Chain: Characterisation, Classical Complexity, Parameterised Complexity and Approximability

Abstract

Access to Document

Handle.net

Fingerprint

Cite this