Algorithmic aspects of disjunctive domination in graphs

DOI10.1007/978-3-319-21398-9_26MaRDI QIDQ3196396zbMATH OpenOpenAlexFDO

Authors B. S. Panda, Arti Pandey, S. Paul

Publication date 29 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.07718

zbMATH Keywords

approximation algorithmgraph algorithmNP-completenessdominationchordal graphAPX-completeness

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: For a graph $G=(V,E)$, a set $DsubseteqV$ is called a emph{disjunctive dominating set} of $G$ if for every vertex $vinVsetminusD$, $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 $gamm{a}_2^d(G)$. The extsc{Minimum Disjunctive Domination Problem} (MDDP) is to find a disjunctive dominating set of cardinality $gamm{a}_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(Delt{a}^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(loglog|V|)})$. Finally, we show that MDDP is APX-complete for bipartite graphs with maximum degree $3$.

Recommendations

• Algorithmic aspects of \(b\)-disjunctive domination in graphs
• B-disjunctive total domination in graphs: algorithm and hardness results
• Algorithmic aspects of disjunctive total domination in graphs
• scientific article; zbMATH DE number 5531984
• Disjoint dominating and 2-dominating sets in graphs

Cites work

• scientific article; zbMATH DE number 4152428 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 4121429 (Why is no real title available?)
• A linear time recognition algorithm for proper interval graphs
• Approximation hardness of dominating set problems in bounded degree graphs
• Disjunctive total domination in graphs
• Dominating sets for split and bipartite graphs
• Domination versus disjunctive domination in trees
• Domination with exponential decay
• Incidence matrices and interval graphs
• On the Kernelization Complexity of Colorful Motifs
• Some APX-completeness results for cubic graphs
• The disjunctive domination number of a graph

Cited in

(10)

• Algorithmic aspects of paired disjunctive domination in graphs
• Dierentiating-Dominating sets in graphs Under binary operations
• Relating domination, exponential domination, and porous exponential domination
• Algorithmic aspects of \(b\)-disjunctive domination in graphs
• Dual domination problems in graphs
• An incremental algorithm for computing ranked full disjunctions
• B-disjunctive total domination in graphs: algorithm and hardness results
• Algorithmic aspects of disjunctive total domination in graphs
• Disjoint dominating and 2-dominating sets in graphs
• On disjunctive domination in graphs

This page was built for publication: Algorithmic aspects of disjunctive domination in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3196396)