- Title
- Algorithmic aspects of upper domination: a parameterised perspective
- Creator
- Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning; Jansen, Klaus; Klein, Kim-Manuel; Lampis, Michael; Liedloff, Mathieu; Monnot, Jérôme; Paschos, Vangelis Th.
- Relation
- 11th International Conference on Algorithmic Aspects in Information and Management (AAIM 2016). 11th International Conference on Algorithmic Aspects in Information and Management [presented in Lecture Notes in Computer Science, Vol. 9778 No. 2016] (Bergamo, Italy 18-20 July, 2016) p. 113-124
- Publisher Link
- http://dx.doi.org/10.1007/978-3-319-41168-2_10
- Publisher
- Springer
- Resource Type
- conference paper
- Date
- 2016
- Description
- This paper studies Upper Domination, i.e., the problem of computing the maximum cardinality of a minimal dominating set in a graph, with a focus on parameterised complexity. Our main results include W[1]-hardness for Upper Domination, contrasting FPT membership for the parameterised dual Co-Upper Domination. The study of structural properties also yields some insight into Upper Total Domination. We further consider graphs of bounded degree and derive upper and lower bounds for kernelisation.
- Subject
- upper domination; maximum cardinality; minimal dominating; parameterised complexity
- Identifier
- http://hdl.handle.net/1959.13/1324518
- Identifier
- uon:25053
- Identifier
- ISBN:9783319411675
- Language
- eng
- Reviewed
- Hits: 5933
- Visitors: 3059
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|