The Library
More results on weighted independent domination
Tools
Tools
Tools
Lozin, Vadim V., Malyshev, Dmitriy, Mosca, Raffaele and Zamaraev, Victor (2017) More results on weighted independent domination. Theoretical Computer Science, 700 . pp. 63-74. doi:10.1016/j.tcs.2017.08.007
|
PDF
WRAP-results-weighted-independent-domination-Lozin-2017.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (659Kb) | Preview |
Official URL: https://doi.org/10.1016/j.tcs.2017.08.007
Abstract
Weighted independent domination is an NP-hard graph problem, which remains computationally intractable in many restricted graph classes. In particular, the problem is NP-hard in the classes of sat-graphs and chordal graphs. We strengthen these results by showing that the problem is NP-hard in a proper subclass of the intersection of sat-graphs and chordal graphs. On the other hand, we identify two new classes of graphs where the problem admits polynomial-time solutions.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||
| Divisions: | Faculty of Science > Mathematics | ||||||||
| Library of Congress Subject Headings (LCSH): | Combinatorial optimization | ||||||||
| Journal or Publication Title: | Theoretical Computer Science | ||||||||
| Publisher: | Elsevier Science BV | ||||||||
| ISSN: | 0304-3975 | ||||||||
| Official Date: | 14 November 2017 | ||||||||
| Dates: |
|
||||||||
| Date of first compliant deposit: | 22 September 2017 | ||||||||
| Volume: | 700 | ||||||||
| Page Range: | pp. 63-74 | ||||||||
| DOI: | 10.1016/j.tcs.2017.08.007 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Funder: | Engineering and Physical Sciences Research Council (EPSRC), Rossiĭskiĭ fond fundamentalʹnykh issledovaniĭ [Russian Foundation for Basic Research] (RFFI), Russia (Federation). President's grant (RFPG), Russia. Национальный исследовательский университет [Higher School of Economics] | ||||||||
| Grant number: | EP/L020408/1 (EPSRC), 16-31-60008-mol-a-d (RFFI), MK-4819.2016 (RFPG) |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
