The k-neighbor domination problem

DOI10.1016/0377-2217(91)90172-RzbMath0734.90045OpenAlexW2056516068MaRDI QIDQ811346

Shiow-Fen Hwang, Gerard Jennhwa Chang

Publication date: 1991

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(91)90172-r

zbMATH Keywords

NP-completeblock graphslinear algorithmk-neighbor dominationminimum cardinality vertex set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Discrete location and assignment (90B80) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

The \(k\)-neighbor, \(r\)-domination problems on interval graphs ⋮ An efficient algorithm to solve the distancek-domination problem on permutation graphs ⋮ Relating the annihilation number and the 2-domination number of block graphs ⋮ Bounds on the 2-domination number ⋮ On \(f\)-domination: polyhedral and algorithmic results

Cites Work

• On a conjecture of Fink and Jacobson concerning k-domination and k- dependence
• Relations between packing and covering numbers of a tree
• State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure
• An upper bound for thek-domination number of a graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The k-neighbor domination problem