Thumbnail - Request a copy

A Boundary Property for Upper Domination

AbouEisha, Hassan; Hussain, Shahid; Lozin, Vadim; Monnot, Jérôme; Ries, Bernard; Zamaraev, Viktor (2016), A Boundary Property for Upper Domination, in Mäkinen, Veli; Puglisi, Simon J.; Salmela, Leena, Combinatorial Algorithms. 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, Proceedings, Springer : Berlin Heidelberg, p. 229-240. 10.1007/978-3-319-44543-4_18

Type
Communication / Conférence
Date
2016
Conference title
27th International Workshop on Combinatorial Algorithms, IWOCA 2016
Conference date
2016-08
Conference city
Helsinki
Conference country
Finland
Book title
Combinatorial Algorithms. 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, Proceedings
Book author
Mäkinen, Veli; Puglisi, Simon J.; Salmela, Leena
Publisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-319-44542-7
Pages
229-240
Publication identifier
Metadata
Show full item record
Author(s)
AbouEisha, Hassan
Center for Numerical Porous Media (NumPor) - King Abdullah University of Science and Technology
Hussain, Shahid
Center for Numerical Porous Media (NumPor) - King Abdullah University of Science and Technology
Lozin, Vadim

Monnot, Jérôme cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ries, Bernard

Zamaraev, Viktor
Abstract (EN)
An upper dominating set in a graph is a minimal (with respect to set inclusion) dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard, but can be solved in polynomial time in some restricted graph classes, such as P4-free graphs or 2K2-free graphs. For classes defined by finitely many forbidden induced subgraphs, the boundary separating difficult instances of the problem from polynomially solvable ones consists of the so called boundary classes. However, none of such classes has been identified so far for the upper dominating set problem. In the present paper, we discover the first boundary class for this problem.
Subjects / Keywords
Graph; algrithm; NP-hard