Algorithmic Aspects of Upper Domination: A Parameterised Perspective

Cristina Bazgan; Ljiljana Brankovic; Katrin Casel; Henning Fernau; Klaus Jansen; Kim-Manuel Klein; Michael Lampis; Mathieu Liedloff; Jérôme Monnot; Vangelis Th Paschos

doi:10.1007/978-3-319-41168-2_10

Algorithmic Aspects of Upper Domination: A Parameterised Perspective

Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Kim-Manuel Klein, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, Vangelis Th Paschos

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Citations (Scopus)

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.

Original language	English
Title of host publication	Algorithmic Aspects in Information and Management: 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings
Editors	Riccardo Dondi, Guillaume Fertin, Giancarlo Mauri
Place of Publication	Cham, Switzerland
Publisher	Springer
Pages	113-124
Edition	1
ISBN (Print)	9783319411675, 9783319411682
DOIs	https://doi.org/10.1007/978-3-319-41168-2_10
Publication status	Published - 2016
Event	AAIM 2016: 11th International Conference on Algorithmic Aspects of Information and Management - University of Bergamo, Bergamo, Italy Duration: 18 Jul 2016 → 20 Jul 2016

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Number	9778
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	AAIM 2016: 11th International Conference on Algorithmic Aspects of Information and Management
City	Bergamo, Italy
Period	18/07/16 → 20/07/16

Access to Document

10.1007/978-3-319-41168-2_10

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

Handle.net

Persistent link

Cite this

Bazgan, C., Brankovic, L., Casel, K., Fernau, H., Jansen, K., Klein, K.-M., Lampis, M., Liedloff, M., Monnot, J., & Paschos, V. T. (2016). Algorithmic Aspects of Upper Domination: A Parameterised Perspective. In R. Dondi, G. Fertin, & G. Mauri (Eds.), Algorithmic Aspects in Information and Management: 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings (1 ed., pp. 113-124). (Lecture Notes in Computer Science; No. 9778). Springer. https://doi.org/10.1007/978-3-319-41168-2_10

Bazgan, Cristina ; Brankovic, Ljiljana ; Casel, Katrin et al. / Algorithmic Aspects of Upper Domination : A Parameterised Perspective. Algorithmic Aspects in Information and Management: 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings. editor / Riccardo Dondi ; Guillaume Fertin ; Giancarlo Mauri. 1. ed. Cham, Switzerland : Springer, 2016. pp. 113-124 (Lecture Notes in Computer Science; 9778).

@inproceedings{b5ab21ce48a347db820dadb8c1ce8832,

title = "Algorithmic Aspects of Upper Domination: A Parameterised Perspective",

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.",

author = "Cristina Bazgan and Ljiljana Brankovic and Katrin Casel and Henning Fernau and Klaus Jansen and Kim-Manuel Klein and Michael Lampis and Mathieu Liedloff and J{\'e}r{\^o}me Monnot and Paschos, \{Vangelis Th\}",

year = "2016",

doi = "10.1007/978-3-319-41168-2\_10",

language = "English",

isbn = "9783319411675",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

number = "9778",

pages = "113--124",

editor = "Riccardo Dondi and Guillaume Fertin and Giancarlo Mauri",

booktitle = "Algorithmic Aspects in Information and Management: 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings",

edition = "1",

note = "AAIM 2016: 11th International Conference on Algorithmic Aspects of Information and Management ; Conference date: 18-07-2016 Through 20-07-2016",

}

Bazgan, C, Brankovic, L, Casel, K, Fernau, H, Jansen, K, Klein, K-M, Lampis, M, Liedloff, M, Monnot, J & Paschos, VT 2016, Algorithmic Aspects of Upper Domination: A Parameterised Perspective. in R Dondi, G Fertin & G Mauri (eds), Algorithmic Aspects in Information and Management: 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings. 1 edn, Lecture Notes in Computer Science, no. 9778, Springer, Cham, Switzerland, pp. 113-124, AAIM 2016: 11th International Conference on Algorithmic Aspects of Information and Management, Bergamo, Italy, 18/07/16. https://doi.org/10.1007/978-3-319-41168-2_10

Algorithmic Aspects of Upper Domination: A Parameterised Perspective. / Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin et al.
Algorithmic Aspects in Information and Management: 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings. ed. / Riccardo Dondi; Guillaume Fertin; Giancarlo Mauri. 1. ed. Cham, Switzerland: Springer, 2016. p. 113-124 (Lecture Notes in Computer Science; No. 9778).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Algorithmic Aspects of Upper Domination

T2 - AAIM 2016: 11th International Conference on Algorithmic Aspects of Information and Management

AU - Bazgan, Cristina

AU - Brankovic, Ljiljana

AU - Casel, Katrin

AU - Fernau, Henning

AU - Jansen, Klaus

AU - Klein, Kim-Manuel

AU - Lampis, Michael

AU - Liedloff, Mathieu

AU - Monnot, Jérôme

AU - Paschos, Vangelis Th

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

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

U2 - 10.1007/978-3-319-41168-2_10

DO - 10.1007/978-3-319-41168-2_10

M3 - Conference contribution

SN - 9783319411675

SN - 9783319411682

T3 - Lecture Notes in Computer Science

SP - 113

EP - 124

BT - Algorithmic Aspects in Information and Management: 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings

A2 - Dondi, Riccardo

A2 - Fertin, Guillaume

A2 - Mauri, Giancarlo

PB - Springer

CY - Cham, Switzerland

Y2 - 18 July 2016 through 20 July 2016

ER -

Bazgan C, Brankovic L, Casel K, Fernau H, Jansen K, Klein KM et al. Algorithmic Aspects of Upper Domination: A Parameterised Perspective. In Dondi R, Fertin G, Mauri G, editors, Algorithmic Aspects in Information and Management: 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings. 1 ed. Cham, Switzerland: Springer. 2016. p. 113-124. (Lecture Notes in Computer Science; 9778). Epub 2016 Jul 5. doi: 10.1007/978-3-319-41168-2_10

Algorithmic Aspects of Upper Domination: A Parameterised Perspective

Abstract

Publication series

Conference

Access to Document

Handle.net

Fingerprint

Cite this