Algorithmic Aspects of Disjunctive Domination in Graphs

DOI10.1007/978-3-319-21398-9_26zbMath1465.68217arXiv1502.07718OpenAlexW2675930808MaRDI QIDQ3196396

Arti Pandey, B. S. Panda, Subhabrata 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

graph algorithmapproximation algorithmNP-completenesschordal graphdominationAPX-completeness

Mathematics Subject Classification ID

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

Related Items (4)

Algorithmic Aspects of Disjunctive Total Domination in Graphs ⋮ Relating domination, exponential domination, and porous exponential domination ⋮ Algorithmic aspects of \(b\)-disjunctive domination in graphs ⋮ b-Disjunctive Total Domination in Graphs: Algorithm and Hardness Results

Cites Work

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

This page was built for publication: Algorithmic Aspects of Disjunctive Domination in Graphs