A Boundary Property for Upper Domination | Zendy

Hassan AbouEisha | Zendy; Shahid Hussain | Zendy; Vadim Lozin | Zendy; Jérôme Monnot | Zendy; Bernard Ries | Zendy; Viktor Zamaraev | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A Boundary Property for Upper Domination

Author(s) -

Hassan AbouEisha,

Shahid Hussain,

Vadim Lozin,

Jérôme Monnot,

Bernard Ries,

Viktor Zamaraev

Publication year - 2016

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

DOI - 10.1007/978-3-319-44543-4_18

Subject(s) - dominating set , mathematics , combinatorics , cardinality (data modeling) , boundary (topology) , graph , class (philosophy) , upper and lower bounds , property (philosophy) , set (abstract data type) , discrete mathematics , computer science , mathematical analysis , philosophy , epistemology , artificial intelligence , vertex (graph theory) , data mining , programming language

LNCS n°9843International audienceAn 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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research