The weighted perfect domination problem

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

Richard Chia-Tung Lee, Chain-Chin Yen

Publication date: 1990

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

zbMATH Keywords

bipartite graphs; trees; chordal graphs; NP-complete; perfect domination; linear algorithm

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

Related Items

THE PARALLEL ALGORITHMS FOR DETERMINING EDGE-PACKING AND EFFICIENT EDGE DOMINATING SETS IN INTERVAL GRAPHS, A tight bound on the number of mobile servers to guarantee transferability among dominating configurations, Solving the weighted efficient edge domination problem on bipartite permutation graphs, Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs, A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs, Weighted efficient domination problem on some perfect graphs, Weighted domination of cocomparability graphs, The bottleneck independent domination on the classes of bipartite graphs and block graphs., Weighted independent perfect domination on cocomparability graphs, The weighted perfect domination problem and its variants

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item