TY - GEN
T1 - A Boundary Property for Upper Domination
AU - AbouEisha, Hassan M.
AU - Hussain, Shahid
AU - Lozin, Vadim
AU - Monnot, Jérôme
AU - Ries, Bernard
AU - Zamaraev, Viktor
N1 - KAUST Repository Item: Exported on 2020-10-01
PY - 2016/8/9
Y1 - 2016/8/9
N2 - 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.
AB - 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.
UR - http://hdl.handle.net/10754/622127
UR - http://link.springer.com/10.1007/978-3-319-44543-4_18
UR - http://www.scopus.com/inward/record.url?scp=84984914874&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-44543-4_18
DO - 10.1007/978-3-319-44543-4_18
M3 - Conference contribution
SN - 9783319445427
SP - 229
EP - 240
BT - Lecture Notes in Computer Science
PB - Springer Nature
ER -