The Library
A boundary property for upper domination
Tools
AbouEisha, Hassan, Hussain, Shahid, Lozin, Vadim V., Monnot, Jérôme, Ries, Bernard and Zamaraev, Viktor (2016) A boundary property for upper domination. In: UNSPECIFIED. Published in: IWOCA 2016: Combinatorial Algorithms, 9843 pp. 229-240. doi:10.1007/978-3-319-44543-4_18 ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-319-44543-4_18
Abstract
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.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | IWOCA 2016: Combinatorial Algorithms | ||||
Publisher: | Springer | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Combinatorial Algorithms | ||||
Official Date: | 2016 | ||||
Dates: |
|
||||
Volume: | 9843 | ||||
Page Range: | pp. 229-240 | ||||
DOI: | 10.1007/978-3-319-44543-4_18 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Conference Paper Type: | Paper | ||||
Type of Event: | Conference |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |