The weighted perfect domination problem and its variants

DOI10.1016/0166-218X(94)00138-4zbMath0848.05042OpenAlexW2165864598MaRDI QIDQ1917310

Chain-Chin Yen, Richard Chia-Tung Lee

Publication date: 6 October 1996

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(94)00138-4

zbMATH Keywords

algorithmscostNP-completeweighted perfect domination problemperfect dominating set

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39)

Related Items (31)

Perfect edge domination and efficient edge domination in graphs ⋮ Uniformity of Point Samples in Metric Spaces Using Gap Ratio ⋮ A dichotomy for weighted efficient dominating sets with bounded degree vertices ⋮ Weighted efficient domination problem on some perfect graphs ⋮ Efficient domination through eigenvalues ⋮ Structure of squares and efficient domination in graph classes ⋮ Classification of efficient dominating sets of circulant graphs of degree 5 ⋮ Perfect Italian domination in graphs: complexity and algorithms ⋮ ON GRAPHS WITH PAIRWISE DISJOINT EFFICIENT DOMINATING SETS AND EFFICIENT DOMINATION IN TREES IN TERMS OF SUPPORT VERTICES ⋮ A linear-time algorithm for weighted paired-domination on block graphs ⋮ Weighted independent perfect domination on cocomparability graphs ⋮ Hereditary Efficiently Dominatable Graphs ⋮ Modelling and solving the perfect edge domination problem ⋮ Weighted domination of cocomparability graphs ⋮ Uniformity of Point Samples in Metric Spaces Using Gap Ratio ⋮ Efficient minus and signed domination in graphs ⋮ Extended formulations for perfect domination problems and their algorithmic implications ⋮ k-Efficient domination: Algorithmic perspective ⋮ Weighted efficient domination in two subclasses of \(P_6\)-free graphs ⋮ On efficiently total dominatable digraphs ⋮ Generalized perfect domination in graphs ⋮ Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs ⋮ Efficient domination for classes of \(P_6\)-free graphs ⋮ Counting independent sets in tree convex bipartite graphs ⋮ Polynomial-time algorithm for weighted efficient domination problem on diameter three planar graphs ⋮ Algorithmic results on double Roman domination in graphs ⋮ Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs ⋮ On efficient domination for some classes of \(H\)-free chordal graphs ⋮ On efficient domination for some classes of \(H\)-free chordal graphs ⋮ Solving the weighted efficient edge domination problem on bipartite permutation graphs ⋮ Efficient \((j, k)\)-dominating functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The weighted perfect domination problem
• Labeling algorithms for domination problems in sun-free chordal graphs
• A linear algorithm for the domination number of a tree
• 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
• Perfect codes in graphs
• On the Algorithmic Complexity of Total Domination
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• A Characterization of Block-Graphs
• R -Domination in Graphs
• Dominating sets in n‐cubes

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