The weighted perfect domination problem

DOI10.1016/0020-0190(90)90031-RzbMath0698.68056MaRDI QIDQ912630

Chain-Chin Yen, Richard Chia-Tung Lee

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

bipartite graphstreeschordal graphsNP-completeperfect dominationlinear algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (21)

A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs ⋮ \((1, j)\)-set problem in graphs ⋮ Weighted efficient domination problem on some perfect graphs ⋮ Structure of squares and efficient domination in graph classes ⋮ A Taxonomy of Perfect Domination ⋮ THE PARALLEL ALGORITHMS FOR DETERMINING EDGE-PACKING AND EFFICIENT EDGE DOMINATING SETS IN INTERVAL GRAPHS ⋮ Structural parameterization for minimum conflict-free colouring ⋮ Weighted independent perfect domination on cocomparability graphs ⋮ The weighted perfect domination problem and its variants ⋮ Weighted domination of cocomparability graphs ⋮ Perfect domination and small cycles ⋮ \([1,2\)-sets in graphs] ⋮ The bottleneck independent domination on the classes of bipartite graphs and block graphs. ⋮ A tight bound on the number of mobile servers to guarantee transferability among dominating configurations ⋮ The \(k\)-power domination problem in weighted trees ⋮ Algorithms for unipolar and generalized split graphs ⋮ Solving the weighted efficient edge domination problem on bipartite permutation graphs ⋮ On \([j, k\)-sets in graphs] ⋮ Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs ⋮ Outer complete fair domination in graphs ⋮ Equitable fair domination in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dominating sets for split and bipartite graphs
• Labeling algorithms for domination problems in sun-free chordal graphs
• The distance-domination numbers of trees
• Optimum domination in weighted trees
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
• Dominating Sets in Chordal Graphs
• Towards a theory of domination in graphs
• Scheduling to Minimize Interaction Cost

This page was built for publication: The weighted perfect domination problem