The weighted perfect domination problem and its variants
type: Item
instance of: scholarly article
title: The weighted perfect domination problem and its variants
zbMATH Open document ID: 0848.05042
DOI: 10.1016/0166-218X(94)00138-4
author: Chain-Chin Yen
author: R. C. T. Lee
published in: Discrete Applied Mathematics
publication date: 1996-10-06T00:00:00Z
review text: A perfect dominating set in a graph \(G\) is a subset \(D\) of the vertex set of \(G\) such that each vertex of \(G\) not in \(D\) is adjacent to exactly one vertex of \(D\). It is supposed that each vertex and each edge of \(G\) is labelled by a number called cost. For a subset \(D\) of the vertex set of \(G\) the total cost is the sum of costs of all vertices of \(D\) and of all edges having exactly one endvertex in \(D\). The weighted perfect domination problem is the problem to find a perfect dominating set \(D\) of \(G\) such that its total cost is minimum. Three variants of this problem are introduced, namely the problem to find a perfect dominating set which is moreover independent (induces a subgraph without edges), connected (induces a connected subgraph) or total (induces a subgraph without isolated vertices). These problems are proved to be NP-complete for bipartite graphs and chordal graphs, except the total perfect domination problem in chordal graphs. For these problems in block graphs linear-time algorithms are presented.
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 897410
zbMATH Keywords: perfect dominating set
zbMATH Keywords: cost
zbMATH Keywords: weighted perfect domination problem
zbMATH Keywords: NP-complete
zbMATH Keywords: algorithms
MaRDI profile type: Publication
cites work: Q4773298
cites work: Q3815323
cites work: Perfect codes in graphs
cites work: Labeling algorithms for domination problems in sun-free chordal graphs
cites work: The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
cites work: Q4268431
cites work: Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
cites work: A linear algorithm for the domination number of a tree
cites work: A Characterization of Block-Graphs
cites work: On the Algorithmic Complexity of Total Domination
cites work: Q3933018
cites work: Q5284096
cites work: R -Domination in Graphs
cites work: Dominating sets in n‐cubes
cites work: The weighted perfect domination problem
cites work: A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs
full work available at URL: 0166-218x(94)00138-4
OpenAlex ID: W2165864598
Recommended article: The weighted perfect domination problem
Recommended article: Weighted efficient domination problem on some perfect graphs
Recommended article: Exact and heuristic algorithms for the weighted total domination problem
Recommended article: On weighted efficient total domination
Recommended article: Extended formulations for perfect domination problems and their algorithmic implications
Recommended article: New Polynomial Cases of the Weighted Efficient Domination Problem
Recommended article: Integer linear programming models for the weighted total domination problem
Recommended article: The \(k\)-power domination problem in weighted trees
Recommended article: The exact weighted independent set problem in perfect graphs and related classes
description: scientific article; zbMATH DE number 897410