|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'503'724
Articles rated: 2609
24 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Complexity and Algorithms for Semipaired Domination in Graphs | | Michael A. Henning
; Arti Pandey
; Vikash Tripathi
; | | Date: |
1 Apr 2019 | | Abstract: | For a graph $G=(V,E)$ with no isolated vertices, a set $Dsubseteq V$ is
called a semipaired dominating set of G if $(i)$ $D$ is a dominating set of
$G$, and $(ii)$ $D$ can be partitioned into two element subsets such that the
vertices in each two element set are at distance at most two. The minimum
cardinality of a semipaired dominating set of $G$ is called the semipaired
domination number of $G$, and is denoted by $gamma_{pr2}(G)$. The
extsc{Minimum Semipaired Domination} problem is to find a semipaired
dominating set of $G$ of cardinality $gamma_{pr2}(G)$. In this paper, we
initiate the algorithmic study of the extsc{Minimum Semipaired Domination}
problem. We show that the decision version of the extsc{Minimum Semipaired
Domination} problem is NP-complete for bipartite graphs and split graphs. On
the positive side, we present a linear-time algorithm to compute a minimum
cardinality semipaired dominating set of interval graphs and trees. We also
propose a $1+ln(2Delta+2)$-approximation algorithm for the extsc{Minimum
Semipaired Domination} problem, where $Delta$ denote the maximum degree of the
graph and show that the extsc{Minimum Semipaired Domination} problem cannot
be approximated within $(1-epsilon) ln|V|$ for any $epsilon > 0$ unless NP
$subseteq$ DTIME$(|V|^{O(loglog|V|)})$. | | Source: | arXiv, 1904.0964 | | 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