Algorithmic aspects of the \(k\)-domination problem in graphs

DOI10.1016/j.dam.2013.01.015zbMath1287.05103OpenAlexW1976882237MaRDI QIDQ2446334

James K. Lan, Gerard Jennhwa Chang

Publication date: 16 April 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.01.015

zbMATH Keywords

treealgorithmsplit graphNP-completeblock graphcactus\(k\)-dominationblock-cactus graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) 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)

Related Items (17)

Tree-Like Structure Graphs with Full Diversity of Balls ⋮ Multiple domination models for placement of electric vehicle charging stations in road networks ⋮ A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph ⋮ Heuristics for \(k\)-domination models of facility location problems in street networks ⋮ A generalized linear time algorithm for an optimal \(k\)-distance dominating set of a weighted tree ⋮ On the algorithmic complexity of \(k\)-tuple total domination ⋮ A linear time algorithm for optimal \(k\)-hop dominating set of a tree ⋮ Computing maximum matchings in temporal graphs ⋮ Domination and convexity problems in the target set selection model ⋮ Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs ⋮ Complexity of \(k\)-rainbow independent domination and some results on the lexicographic product of graphs ⋮ Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs ⋮ The strong domination problem in block graphs and proper interval graphs ⋮ Multiple Domination ⋮ New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs ⋮ A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs ⋮ Enumeration of labeled block-cactus graphs

Cites Work

• \(k\)-domination and \(k\)-independence in graphs: A survey
• A note on the k-domination number of a graph
• Upper bounds on the \(k\)-domination number and the \(k\)-Roman domination number
• A linear algorithm for finding a minimum dominating set in a cactus
• A linear algorithm for the domination number of a tree
• Upper bounds for \(f\)-domination number of graphs
• Algorithmic aspect of \(k\)-tuple domination in graphs.
• Onk-domination and minimum degree in graphs
• An upper bound for thek-domination number of a graph
• A new domination conception
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Algorithmic aspects of the \(k\)-domination problem in graphs