Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs

DOI10.1016/0020-0190(93)90147-2zbMath0787.68077OpenAlexW1969612844MaRDI QIDQ1313745

Yi-Chang Liu, Maw-Shang Chang

Publication date: 24 February 1994

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

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90147-2

zbMATH Keywords

chordal graphssplit graphslinear algorithmsperfect domination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (max. 100)

Weighted efficient domination problem on some perfect graphs ⋮ A Taxonomy of Perfect Domination ⋮ Weighted independent perfect domination on cocomparability graphs ⋮ The weighted perfect domination problem and its variants ⋮ Hereditary Efficiently Dominatable Graphs ⋮ Weighted domination of cocomparability graphs ⋮ Efficient minus and signed domination in graphs ⋮ Weighted efficient domination in two subclasses of \(P_6\)-free graphs ⋮ Independent dominating set problem revisited ⋮ Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs ⋮ The \(k\)-power domination problem in weighted trees ⋮ Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs ⋮ Algorithms for unipolar and generalized split graphs ⋮ On efficient domination for some classes of \(H\)-free chordal graphs ⋮ Solving the weighted efficient edge domination problem on bipartite permutation graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The weighted perfect domination problem
• Perfect codes over graphs
• Nearly perfect sets in graphs
• Perfect codes in the graphs \(O_k\)
• Perfect codes in graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Algorithmic Aspects of Vertex Elimination on Graphs

This page was built for publication: Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs