| Author(s) |
Bazgan, Cristina
Brankovic, Ljiljana
Casel, Katrin
Fernau, Henning
|
| Publication Date |
2020-06-15
|
| Abstract |
<p>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.</p>
|
| Citation |
Discrete Applied Mathematics, v.280, p. 23-42
|
| ISSN |
1872-6771
0166-218X
|
| Link | |
| Language |
en
|
| Publisher |
Elsevier BV, North-Holland
|
| Title |
Domination Chain: Characterisation, Classical Complexity, Parameterised Complexity and Approximability
|
| Type of document |
Conference Publication
|
| Entity Type |
Publication
|
| Name | Size | format | Description | Link |
|---|