|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'503'724
Articles rated: 2609
23 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Algorithm and hardness results on neighborhood total domination in graphs | | Anupriya Jha
; D. Pradhan
; S. Banerjee
; | | Date: |
14 Oct 2019 | | Abstract: | A set $Dsubseteq V$ of a graph $G=(V,E)$ is called a neighborhood total
dominating set of $G$ if $D$ is a dominating set and the subgraph of $G$
induced by the open neighborhood of $D$ has no isolated vertex. Given a graph
$G$, extsc{Min-NTDS} is the problem of finding a neighborhood total
dominating set of $G$ of minimum cardinality. The decision version of
extsc{Min-NTDS} is known to be extsf{NP}-complete for bipartite graphs and
chordal graphs. In this paper, we extend this extsf{NP}-completeness result
to undirected path graphs, chordal bipartite graphs, and planar graphs. We also
present a linear time algorithm for computing a minimum neighborhood total
dominating set in proper interval graphs. We show that for a given graph
$G=(V,E)$, extsc{Min-NTDS} cannot be approximated within a factor of
$(1-varepsilon)log |V|$, unless extsf{NP$subseteq$DTIME($|V|^{O(log log
|V|)}$)} and can be approximated within a factor of $O(log Delta)$, where
$Delta$ is the maximum degree of the graph $G$. Finally, we show that
extsc{Min-NTDS} is extsf{APX}-complete for graphs of degree at most $3$. | | Source: | arXiv, 1910.6423 | | 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