Algorithmic aspects of \(b\)-disjunctive domination in graphs

DOI10.1007/s10878-017-0112-6zbMath1402.90198OpenAlexW1542353215MaRDI QIDQ721940

Arti Pandey, B. S. Panda, Subhabrata Paul

Publication date: 20 July 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-017-0112-6

zbMATH Keywords

graph algorithmapproximation algorithmchordal graphNP-completedominationAPX-complete

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (11)

Total vertex-edge domination in graphs: Complexity and algorithms ⋮ Complexity aspects of variants of independent Roman domination in graphs ⋮ Disjunctive domination in graphs with minimum degree at least two ⋮ Algorithmic aspects of outer independent Roman domination in graphs ⋮ Algorithmic aspects of paired disjunctive domination in graphs ⋮ Algorithmic Aspects of Outer-Independent Total Roman Domination in Graphs ⋮ Unnamed Item ⋮ Algorithmic aspects of total Roman ${2}$-domination in graphs ⋮ Algorithmic aspects of secure connected domination in graphs ⋮ Algorithmic complexity of weakly connected Roman domination in graphs ⋮ Algorithmic aspects of total Roman {3}-domination in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Disjunctive total domination in graphs
• Dominating sets for split and bipartite graphs
• Bounds on the disjunctive total domination number of a tree
• 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
• b-Disjunctive Total Domination in Graphs: Algorithm and Hardness Results
• The disjunctive domination number of a graph
• On the Kernelization Complexity of Colorful Motifs
• Algorithmic Aspects of Disjunctive Domination in Graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• A constructive characterization of trees with equal total domination and disjunctive domination numbers
• Graphs with Large Disjunctive Total Domination Number

This page was built for publication: Algorithmic aspects of \(b\)-disjunctive domination in graphs