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

DOI10.1016/0020-0190(93)90147-2MaRDI QIDQ1313745zbMATH OpenOpenAlexFDO

Authors Maw-Shang Chang, Yichang Liu

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

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

Recommendations

• Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
• New polynomial cases of the weighted efficient domination problem
• Weighted efficient domination problem on some perfect graphs
• Polynomial algorithms for some hard problems of finding connected spanning subgraphs of extreme total edge weight
• Polynomial-time algorithm for weighted efficient domination problem on diameter three planar graphs
• Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract)
• scientific article; zbMATH DE number 3882470
• A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs
• The weighted perfect domination problem and its variants
• scientific article; zbMATH DE number 12050

Cites work

• scientific article; zbMATH DE number 4085682 (Why is no real title available?)
• scientific article; zbMATH DE number 91051 (Why is no real title available?)
• scientific article; zbMATH DE number 933213 (Why is no real title available?)
• scientific article; zbMATH DE number 975419 (Why is no real title available?)
• Algorithmic Aspects of Vertex Elimination on Graphs
• Nearly perfect sets in graphs
• Perfect codes in graphs
• Perfect codes in the graphs \(O_k\)
• Perfect codes over graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The weighted perfect domination problem

Cited in

(18)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1313745)