1. Research UNE
  2. UNE
  3. Conference Publication
Please use this identifier to cite or link to this item: https://hdl.handle.net/1959.11/52012
Title: Algorithmic Aspects of Upper Domination: A Parameterised Perspective
Contributor(s): Bazgan, Cristina (author); Brankovic, Ljiljana  (author)orcid ; Casel, Katrin (author); Fernau, Henning (author); Jansen, Klaus (author); Klein, Kim-Manuel (author); Lampis, Michael (author); Liedloff, Mathieu (author); Monnot, Jérôme (author); Paschos, Vangelis Th (author)
Publication Date: 2016
DOI: 10.1007/978-3-319-41168-2_10
Handle Link: https://hdl.handle.net/1959.11/52012
Abstract: 

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.

Publication Type: Conference Publication
Conference Details: AAIM 2016: 11th International Conference on Algorithmic Aspects of Information and Management, Bergamo, Italy, 18th - 20th July, 2016.
Source of Publication: Algorithmic Aspects in Information and Management: 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings, p. 113-124
Publisher: Springer
Place of Publication: Cham, Switzerland
Fields of Research (FoR) 2020: 390113 Science, technology and engineering curriculum and pedagogy
Socio-Economic Objective (SEO) 2020: 160399 Teaching and curriculum not elsewhere classified
Peer Reviewed: Yes
HERDC Category Description: E1 Refereed Scholarly Conference Publication
Series Name: Lecture Notes in Computer Science
Series Number : 9778
Appears in Collections:Conference Publication
School of Science and Technology

Files in This Item:
4 files
File Description SizeFormat 
Show full item record

SCOPUSTM   
Citations

4
checked on Mar 16, 2024

Page view(s)

1,088
checked on Mar 9, 2023

Download(s)

6
checked on Mar 9, 2023
Google Media

Google ScholarTM

Check

Altmetric


Items in Research UNE are protected by copyright, with all rights reserved, unless otherwise indicated.