Mim-width. III. Graph powers and generalized distance domination problems

DOI10.1016/j.tcs.2019.09.012zbMath1442.05157OpenAlexW2972989051MaRDI QIDQ2333800

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

Publication date: 13 November 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.09.012

zbMATH Keywords

parameterized complexitygraph classesleaf powersgraph powersgraph width parametersdistance domination problems

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (22)

Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Mim-width. I. Induced path problems ⋮ Recognition of linear and star variants of leaf powers is in P ⋮ Bounding the mim‐width of hereditary graph classes ⋮ Recognizing k -Leaf Powers in Polynomial Time, for Constant k ⋮ The statistical analysis for Sombor indices in a random polygonal chain networks ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ On the tractability of optimization problems on \(H\)-graphs ⋮ Classes of intersection digraphs with good algorithmic properties ⋮ Unnamed Item ⋮ On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs ⋮ List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective ⋮ Recognizing Proper Tree-Graphs ⋮ Bounding the Mim-Width of Hereditary Graph Classes. ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Unnamed Item ⋮ Distance Domination in Graphs ⋮ Mim-width. III. Graph powers and generalized distance domination problems ⋮ Revising Johnson's table for the 21st century ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width ⋮ Vertex cover at distance on \(H\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clique-width of path powers
• Towards a characterization of leaf powers by clique arrangements
• Graph classes with structured neighborhoods and algorithmic applications
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Characterising \((k,\ell )\)-leaf powers
• On the parameterized complexity of multiple-interval graph problems
• Treewidth. Computations and approximations
• Powers of geometric intersection graphs and dispersion algorithms
• Improved algorithms for \(k\)-domination and total \(k\)-domination in proper interval graphs
• On strongly chordal graphs that are not leaf powers
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• On powers of \(m\)-trapezoid graphs
• Mim-width. II. The feedback vertex set problem
• Mim-width. III. Graph powers and generalized distance domination problems
• Lower bounds on the mim-width of some graph classes
• Perfect codes in graphs
• The point-set embeddability problem for plane graphs
• Pairwise Compatibility Graphs: A Survey
• R -Domination in Graphs
• Graph Classes: A Survey
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• An efficient algorithm to solve the distancek-domination problem on permutation graphs
• Hardness of computing width parameters based on branch decompositions over the vertex set
• On \(H\)-topological intersection graphs

This page was built for publication: Mim-width. III. Graph powers and generalized distance domination problems