Algorithmic aspects of disjunctive domination in graphs

DOI10.1007/978-3-319-21398-9_26zbMATH Open1465.68217arXiv1502.07718OpenAlexW2675930808MaRDI QIDQ3196396FDOQ3196396

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

Publication date: 29 October 2015

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

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$.

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

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
• Disjoint dominating and 2-dominating sets in graphs

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Some APX-completeness results for cubic graphs
• Incidence matrices and interval graphs
• Disjunctive total domination in graphs
• The disjunctive domination number of a graph
• Title not available (Why is that?)
• Dominating sets for split and bipartite graphs
• On the Kernelization Complexity of Colorful Motifs
• Approximation hardness of dominating set problems in bounded degree graphs
• Title not available (Why is that?)
• A linear time recognition algorithm for proper interval graphs
• Title not available (Why is that?)
• Domination with exponential decay
• Domination versus disjunctive domination in trees

Cited In (7)

• Dierentiating-Dominating sets in graphs Under binary operations
• Relating domination, exponential domination, and porous exponential domination
• Algorithmic aspects of \(b\)-disjunctive domination 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
• 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)