Structurally parameterized \(d\)-scattered set
type: Item
instance of: scholarly article
title: Structurally parameterized \(d\)-scattered set
zbMATH Open document ID: 1479.05081
author: Ioannis Katsikarelis
author: Michael Lampis
author: Vangelis Th. Paschos
published in: Discrete Applied Mathematics
publication date: 2022-01-05T00:00:00Z
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7452364
zbMATH Keywords: independence
zbMATH Keywords: treewidth
zbMATH Keywords: SETH
zbMATH Keywords: distance parameter
MaRDI profile type: Publication
full work available at URL: j.dam.2020.03.052
OpenAlex ID: W3015605341
cites work: Parameterized Power Vertex Cover
cites work: Fourier meets M\"{o}bius: fast subset convolution
cites work: The algorithmic theory of treewidth
cites work: Treewidth: Characterizations, Applications, and Computations
cites work: Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
cites work: Parallel Algorithms with Optimal Speedup for Bounded Treewidth
cites work: Scheduling of pipelined operator graphs
cites work: Faster Algorithms on Branch and Clique Decompositions
cites work: Optimal dynamic program for r-domination problems over tree decompositions
cites work: Upper bounds to the clique width of graphs
cites work: Parameterized Algorithms
cites work: Fundamentals of parameterized complexity
cites work: Distance-\(d\) independent set problems for bipartite and chordal graphs
cites work: Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
cites work: Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs
cites work: Parametrized complexity theory.
cites work: Q5365078
cites work: Independent sets with domination constraints
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: On the complexity of \(k\)-SAT
cites work: Which problems have strongly exponential complexity?
cites work: Structural parameters, tight bounds, and approximation for \((k, r)\)-center
cites work: Treewidth. Computations and approximations
cites work: Parameterized Approximation Schemes Using Graph Widths
cites work: Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
cites work: Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
cites work: On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators
cites work: Tree-depth, subgraph coloring and homomorphism bounds
cites work: Mixed searching and proper-path-width
cites work: Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
DOI: 10.1016/J.DAM.2020.03.052
description: scientific article; zbMATH DE number 7452364