|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
27 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Algorithmic aspects of disjunctive domination in graphs | | B.S. Panda
; Arti Pandey
; | | Date: |
26 Feb 2015 | | Abstract: | For a graph $G=(V,E)$, a set $Dsubseteq V$ is called a emph{disjunctive
dominating set} of $G$ if for every vertex $vin Vsetminus D$, $v$ is either
adjacent to a vertex of $D$ or has at least two vertices in $D$ at distance $2$
from it. The cardinality of a minimum disjunctive dominating set of $G$ is
called the emph{disjunctive domination number} of graph $G$, and is denoted by
$gamma_{2}^{d}(G)$. The extsc{Minimum Disjunctive Domination Problem} (MDDP)
is to find a disjunctive dominating set of cardinality $gamma_{2}^{d}(G)$.
Given a positive integer $k$ and a graph $G$, the extsc{Disjunctive
Domination Decision Problem} (DDDP) is to decide whether $G$ has a disjunctive
dominating set of cardinality at most $k$. In this article, we first propose a
linear time algorithm for MDDP in proper interval graphs. Next we tighten the
NP-completeness of DDDP by showing that it remains NP-complete even in chordal
graphs. We also propose a $(ln(Delta^{2}+Delta+2)+1)$-approximation
algorithm for MDDP in general graphs and prove that MDDP can not be
approximated within $(1-epsilon) ln(|V|)$ for any $epsilon>0$ unless NP
$subseteq$ DTIME$(|V|^{O(log log |V|)})$. Finally, we show that MDDP is
APX-complete for bipartite graphs with maximum degree $3$. | | Source: | arXiv, 1502.7718 | | 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