Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
From MaRDI portal
Publication:477653
DOI10.1016/j.ipl.2014.09.024zbMath1304.05104arXiv1410.0770OpenAlexW1973932399MaRDI QIDQ477653
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)
Full work available at URL: https://arxiv.org/abs/1410.0770
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)
Related Items
A dichotomy for weighted efficient dominating sets with bounded degree vertices ⋮ Weighted Efficient Domination for $$P_6$$ -Free and for $$P_5$$ -Free Graphs ⋮ 2-divisibility of some odd hole free graphs ⋮ Structure of squares and efficient domination in graph classes ⋮ Weighted Efficient Domination for $P_5$-Free and $P_6$-Free Graphs ⋮ On Strong Tree-Breadth ⋮ Weighted efficient domination in two subclasses of \(P_6\)-free graphs ⋮ Graphs that are simultaneously efficient open domination and efficient closed domination graphs ⋮ Efficient domination for classes of \(P_6\)-free graphs ⋮ The (non-)existence of perfect codes in Fibonacci cubes ⋮ Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications ⋮ 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 ⋮ On efficient domination for some classes of \(H\)-free chordal graphs ⋮ On efficient domination for some classes of \(H\)-free chordal graphs ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width ⋮ Efficient Domination for Some Subclasses of $$P_6$$ -free Graphs in Polynomial Time ⋮ On efficient domination for some classes of \(H\)-free bipartite graphs
Cites Work
- On maximal independent sets of vertices in claw-free graphs
- Modular decomposition and transitive orientation
- Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
- Weighted efficient domination problem on some perfect graphs
- Weighted domination of cocomparability graphs
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- Perfect Code is \(W[1\)-complete]
- Algorithmic graph theory and perfect graphs
- Weighted independent perfect domination on cocomparability graphs
- The weighted perfect domination problem and its variants
- Linear time solvable optimization problems on graphs of bounded clique-width
- Perfect codes in graphs
- A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
- Efficient Edge Domination on Hole-Free Graphs in Polynomial Time
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Dually Chordal Graphs
- Graph Classes: A Survey
- Independent Sets in Asteroidal Triple-Free Graphs
- Asteroidal Triple-Free Graphs
- A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
- Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs
- Hereditary Efficiently Dominatable Graphs
- Multiplying matrices faster than coppersmith-winograd
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
