|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
A linear kernel for planar total dominating set | | Valentin Garnero
; Ignasi Sau
; | | Date: |
5 Nov 2012 | | Abstract: | A "total dominating set" of a graph G=(V,E) is a subset D of V such that
every vertex in V is adjacent to some vertex in D. Finding a total dominating
set of minimum size is NP-complete on planar graphs and W[2]-complete on
general graphs when parameterized by the solution size. By the meta-theorem of
Bodlaender et al. [FOCS 2009], it follows that there exists a linear kernel for
Total Dominating Set on graphs of bounded genus. Nevertheless, it is not clear
how such a kernel can be effectively constructed, and how to obtain explicit
reduction rules with reasonably small constants. Following the approach of
Alber et al. [J. ACM 2004], we provide an explicit linear kernel for Total
Dominating Set on planar graphs. This result complements several known
constructive linear kernels on planar graphs for other domination problems such
as Dominating Set, Edge Dominating Set, Efficient Dominating Set, or Connected
Dominating Set. | | Source: | arXiv, 1211.0978 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER