Mim-width. III. Graph powers and generalized distance domination problems
type: Item
instance of: scholarly article
title: Mim-width. III. Graph powers and generalized distance domination problems
zbMATH Open document ID: 1442.05157
author: Lars Jaffke
author: O-joung Kwon
author: Torstein J. F. Strømme
author: Jan Arne Telle
published in: Theoretical Computer Science
publication date: 2019-11-13T00:00:00Z
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 68Q27
zbMATH DE Number: 7129476
zbMATH Keywords: graph width parameters
zbMATH Keywords: graph classes
zbMATH Keywords: distance domination problems
zbMATH Keywords: parameterized complexity
zbMATH Keywords: graph powers
zbMATH Keywords: leaf powers
MaRDI profile type: Publication
full work available at URL: j.tcs.2019.09.012
OpenAlex ID: W2972989051
cites work: Powers of geometric intersection graphs and dispersion algorithms
cites work: Q4634386
cites work: Graph classes with structured neighborhoods and algorithmic applications
cites work: Perfect codes in graphs
cites work: Graph Classes: A Survey
cites work: Characterising \((k,\ell )\)-leaf powers
cites work: Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
cites work: Pairwise Compatibility Graphs: A Survey
cites work: On \(H\)-topological intersection graphs
cites work: Improved algorithms for \(k\)-domination and total \(k\)-domination in proper interval graphs
cites work: On the parameterized complexity of multiple-interval graph problems
cites work: On powers of \(m\)-trapezoid graphs
cites work: Q5009589
cites work: Clique-width of path powers
cites work: Q4029974
cites work: Q5009468
cites work: Q5111880
cites work: Mim-width. II. The feedback vertex set problem
cites work: Q3304141
cites work: Treewidth. Computations and approximations
cites work: On strongly chordal graphs that are not leaf powers
cites work: Lower bounds on the mim-width of some graph classes
cites work: Towards a characterization of leaf powers by clique arrangements
cites work: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
cites work: An efficient algorithm to solve the distancek-domination problem on permutation graphs
cites work: Q4032992
cites work: Hardness of computing width parameters based on branch decompositions over the vertex set
cites work: R -Domination in Graphs
cites work: Algorithms for Vertex Partitioning Problems on Partial k-Trees
cites work: The point-set embeddability problem for plane graphs
DOI: 10.1016/J.TCS.2019.09.012
Recommended article: Q5009468
Recommended article: Lower bounds on the mim-width of some graph classes
Recommended article: Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
Recommended article: Solving problems on generalized convex graphs via mim-width
Recommended article: Mim-width. II. The feedback vertex set problem
Recommended article: On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs
Recommended article: Bounding the Mim-Width of Hereditary Graph Classes.
Recommended article: Bounding the mim‐width of hereditary graph classes
Recommended article: On \(d\)-distance \(m\)-tuple \((\ell,r)\)-domination in graphs
Recommended article: On powers of graphs of bounded NLC-width (clique-width)
description: scientific article