The k-neighbor domination problem

DOI10.1016/0377-2217(91)90172-RMaRDI QIDQ811346zbMATH OpenOpenAlexFDO

Authors 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

block graphsk-neighbor dominationlinear algorithmminimum cardinality vertex setNP-complete

Mathematics Subject Classification ID

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

Recommendations

• Algorithmic aspects of the \(k\)-domination problem in graphs
• A labeling algorithm for distance domination on block graphs
• The k-neighbor, r-domination problems on interval graphs
• Labeling algorithms for domination problems in sun-free chordal graphs
• \(k\)-tuple domination in graphs

Cites work

• An upper bound for thek-domination number of a graph
• scientific article; zbMATH DE number 3914370 (Why is no real title available?)
• scientific article; zbMATH DE number 3914371 (Why is no real title available?)
• scientific article; zbMATH DE number 3503127 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2544 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• 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

Cited in

(8)

• The k-neighbor, r-domination problems on interval 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
• Algorithmic aspects of the \(k\)-domination problem in graphs
• A labeling algorithm for distance domination on block graphs
• An efficient algorithm to solve the distance \(k\)-domination problem on permutation graphs
• Heuristics for the weighted total domination problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q811346)