The Library
Upper domination : towards a dichotomy through boundary properties
Tools
Tools
Tools
AbouEisha, Hassan, Hussain, Shahid, Lozin, Vadim V., Monnot, Jérôme, Ries, Bernard and Zamaraev, Victor (2018) Upper domination : towards a dichotomy through boundary properties. Algorithmica, 80 (10). pp. 2799-2817. doi:10.1007/s00453-017-0346-9 ISSN 0178-4617.
|
PDF
WRAP-upper-domination-towards-dichotomy-through-boundary-properties-Lozin-2017.pdf - Accepted Version - Requires a PDF viewer. Download (627Kb) | Preview |
Official URL: https://doi.org/10.1007/s00453-017-0346-9
Abstract
An upper dominating set in a graph is a minimal dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard. We study the complexity of this problem in finitely defined classes of graphs and conjecture that the problem admits a complexity dichotomy in this family. A helpful tool to study the complexity of an algorithmic problem is the notion of boundary classes. However, none of such classes has been identified so far for the upper dominating set problem. We discover the first boundary class for this problem and prove the dichotomy for monogenic classes.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
| Library of Congress Subject Headings (LCSH): | Graph theory, Algorithms | ||||||||
| Journal or Publication Title: | Algorithmica | ||||||||
| Publisher: | Springer Verlag | ||||||||
| ISSN: | 0178-4617 | ||||||||
| Official Date: | October 2018 | ||||||||
| Dates: |
|
||||||||
| Volume: | 80 | ||||||||
| Number: | 10 | ||||||||
| Page Range: | pp. 2799-2817 | ||||||||
| DOI: | 10.1007/s00453-017-0346-9 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Date of first compliant deposit: | 17 July 2017 | ||||||||
| Date of first compliant Open Access: | 14 July 2018 | ||||||||
| RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
