Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
DOI10.1016/0020-0190(93)90147-2zbMATH Open0787.68077OpenAlexW1969612844MaRDI QIDQ1313745FDOQ1313745
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
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
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Perfect codes in graphs
- Title not available (Why is that?)
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Nearly perfect sets in graphs
- Title not available (Why is that?)
- The weighted perfect domination problem
- Perfect codes in the graphs \(O_k\)
- Title not available (Why is that?)
- Perfect codes over graphs
- Title not available (Why is that?)
Cited In (18)
- Efficient minus and signed domination in graphs
- Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs
- Weighted domination of cocomparability graphs
- A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs
- Weighted domination on cocomparability graphs
- The weighted perfect domination problem
- Algorithms for unipolar and generalized split graphs
- A Taxonomy of Perfect Domination
- The \(k\)-power domination problem in weighted trees
- On efficient domination for some classes of \(H\)-free chordal graphs
- Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
- Independent dominating set problem revisited
- Solving the weighted efficient edge domination problem on bipartite permutation graphs
- Weighted efficient domination problem on some perfect graphs
- Weighted efficient domination in two subclasses of \(P_6\)-free graphs
- Hereditary efficiently dominatable graphs
- The weighted perfect domination problem and its variants
- Weighted independent perfect domination on cocomparability 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)
