Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
From MaRDI portal
(Redirected from Publication:477653)
Abstract: An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the vertex set of the graph. The minimum weight efficient domination problem is the problem of finding an efficient dominating set of minimum weight in a given vertex-weighted graph; the maximum weight efficient domination problem is defined similarly. We develop a framework for solving the weighted efficient domination problems based on a reduction to the maximum weight independent set problem in the square of the input graph. Using this approach, we improve on several previous results from the literature by deriving polynomial-time algorithms for the weighted efficient domination problems in the classes of dually chordal and AT-free graphs. In particular, this answers a question by Lu and Tang regarding the complexity of the minimum weight efficient domination problem in strongly chordal graphs.
Recommendations
- New polynomial cases of the weighted efficient domination problem
- On efficient domination for some classes of \(H\)-free chordal graphs
- Polynomial-time algorithm for weighted efficient domination problem on diameter three planar graphs
- Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs
- Weighted efficient domination problem on some perfect graphs
Cites work
- scientific article; zbMATH DE number 3882470 (Why is no real title available?)
- 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 3513839 (Why is no real title available?)
- scientific article; zbMATH DE number 1303039 (Why is no real title available?)
- scientific article; zbMATH DE number 3445275 (Why is no real title available?)
- scientific article; zbMATH DE number 794265 (Why is no real title available?)
- scientific article; zbMATH DE number 921905 (Why is no real title available?)
- scientific article; zbMATH DE number 975419 (Why is no real title available?)
- scientific article; zbMATH DE number 2191988 (Why is no real title available?)
- A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
- A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
- Algorithmic graph theory and perfect graphs
- Asteroidal Triple-Free Graphs
- Dually Chordal Graphs
- Efficient dominating and edge dominating sets for graphs and hypergraphs
- Efficient edge domination on hole-free graphs in polynomial time
- Graph Classes: A Survey
- Hereditary efficiently dominatable graphs
- Independent Sets in Asteroidal Triple-Free Graphs
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Modular decomposition and transitive orientation
- Multiplying matrices faster than coppersmith-winograd
- On maximal independent sets of vertices in claw-free graphs
- Perfect Code is \(W[1]\)-complete
- Perfect codes and independent dominating sets
- Perfect codes in graphs
- Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- The weighted perfect domination problem and its variants
- Weighted domination of cocomparability graphs
- Weighted efficient domination problem on some perfect graphs
- Weighted independent perfect domination on cocomparability graphs
Cited in
(20)- On efficient domination for some classes of \(H\)-free bipartite graphs
- Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs
- Weighted efficient domination for \(P_6\)-free and for \(P_5\)-free graphs
- Efficient domination for some subclasses of \(P_6\)-free graphs in polynomial time
- Domination, independent domination, and duality in strongly chordal graphs
- Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
- A dichotomy for weighted efficient dominating sets with bounded degree vertices
- On strong tree-breadth
- On efficient domination for some classes of \(H\)-free chordal graphs
- The (non-)existence of perfect codes in Fibonacci cubes
- 2-divisibility of some odd hole free graphs
- Structure of squares and efficient domination in graph classes
- Polynomial-time algorithm for weighted efficient domination problem on diameter three planar graphs
- On efficient domination for some classes of \(H\)-free chordal graphs
- Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications
- Weighted efficient domination for \(P_5\)-free and \(P_6\)-free graphs
- Weighted efficient domination in two subclasses of P₆-free graphs
- Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
- Graphs that are simultaneously efficient open domination and efficient closed domination graphs
- Efficient domination for classes of \(P_6\)-free graphs
This page was built for publication: Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477653)
