Generalized distance domination problems and their complexity on graphs of bounded mim-width

DOI10.4230/LIPICS.IPEC.2018.6MaRDI QIDQ5009468zbMATH OpenFDO

Authors Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, Jan Arne Telle

Publication date 4 August 2021

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

zbMATH Keywords

distance domination problemsgraph classesgraph width parametersparameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx)

Recommendations

• Mim-width. III. Graph powers and generalized distance domination problems
• Bounding the mim‐width of hereditary graph classes
• Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
• Mim-width. I. Induced path problems

Cites work

• R -Domination in Graphs
• A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• An efficient algorithm to solve the distance \(k\)-domination problem on permutation graphs
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Graph classes with structured neighborhoods and algorithmic applications
• Graph Classes: A Survey
• H-free graphs, independent sets, and subexponential-time algorithms
• Hardness of computing width parameters based on branch decompositions over the vertex set
• scientific article; zbMATH DE number 146666 (Why is no real title available?)
• scientific article; zbMATH DE number 165077 (Why is no real title available?)
• Mim-width. III. Graph powers and generalized distance domination problems
• On \(H\)-topological intersection graphs
• On powers of m-trapezoid graphs
• On the parameterized complexity of multiple-interval graph problems
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• On the tractability of optimization problems on \(H\)-graphs
• Perfect codes in graphs
• Powers of geometric intersection graphs and dispersion algorithms
• The point-set embeddability problem for plane graphs

Cited in

(8)

• A new approach on locally checkable problems
• Mim-width. II. The feedback vertex set problem
• Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
• Mim-width. III. Graph powers and generalized distance domination problems
• Distance domination in graphs
• On \(d\)-stable locally checkable problems parameterized by mim-width
• Generalized distance domination problems and their complexity on graphs of bounded mim-width
• Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. I: Algorithmic results

This page was built for publication: Generalized distance domination problems and their complexity on graphs of bounded mim-width

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