Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs

DOI10.1016/J.IPL.2014.09.024zbMATH Open1304.05104arXiv1410.0770OpenAlexW1973932399MaRDI QIDQ477653FDOQ477653

Pavel Fičur, Martin Milanič, Andreas Brandstädt, Arne Leitert

Publication date: 9 December 2014

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

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.

Full work available at URL: https://arxiv.org/abs/1410.0770

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

zbMATH Keywords

graph algorithmsdually chordal graphefficient dominationAT-free graphweighted efficient domination

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Cites Work

• Graph Classes: A Survey
• Modular decomposition and transitive orientation
• Algorithmic graph theory and perfect graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Perfect codes in graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multiplying matrices faster than coppersmith-winograd
• On maximal independent sets of vertices in claw-free graphs
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• Dually Chordal Graphs
• Asteroidal Triple-Free Graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• Weighted efficient domination problem on some perfect graphs
• Perfect Code is \(W[1]\)-complete
• Weighted independent perfect domination on cocomparability graphs
• The weighted perfect domination problem and its variants
• Efficient Edge Domination on Hole-Free Graphs in Polynomial Time
• Title not available (Why is that?)
• Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs
• Hereditary Efficiently Dominatable Graphs
• Independent Sets in Asteroidal Triple-Free Graphs
• Title not available (Why is that?)
• A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
• Title not available (Why is that?)
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Weighted domination of cocomparability graphs
• Title not available (Why is that?)
• Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
• Perfect codes and independent dominating sets
• Title not available (Why is that?)

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
• 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 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
• Efficient Domination for Some Subclasses of $$P_6$$ -free Graphs in Polynomial Time
• On efficient domination for some classes of \(H\)-free chordal graphs
• Weighted Efficient Domination for $$P_6$$ -Free and for $$P_5$$ -Free Graphs
• Polynomial-time algorithm for weighted efficient domination problem on diameter three planar graphs
• Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications
• On Strong Tree-Breadth
• Weighted efficient domination in two subclasses of \(P_6\)-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
• Weighted Efficient Domination for $P_5$-Free and $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)