Algorithmic aspects of upper domination: a parameterised perspective

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

		Thumbnail	File	Description	Size	Format