Structurally parameterized \(d\)-scattered set
From MaRDI portal
Publication:2064293
DOI10.1016/j.dam.2020.03.052zbMath1479.05081OpenAlexW3015605341MaRDI QIDQ2064293
Vangelis Th. Paschos, Ioannis Katsikarelis, Michael Lampis
Publication date: 5 January 2022
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2020.03.052
Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (3)
On the complexity of distance-\(d\) independent set reconfiguration ⋮ Improved (In-)Approximability Bounds for d-Scattered Set ⋮ On the tree-depth and tree-width in heterogeneous random graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Mixed searching and proper-path-width
- Treewidth. Computations and approximations
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Which problems have strongly exponential complexity?
- Independent sets with domination constraints
- Upper bounds to the clique width of graphs
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- Scheduling of pipelined operator graphs
- Distance-\(d\) independent set problems for bipartite and chordal graphs
- Parametrized complexity theory.
- Tree-depth, subgraph coloring and homomorphism bounds
- Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
- Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs
- Parameterized Power Vertex Cover
- On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators
- Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
- Treewidth: Characterizations, Applications, and Computations
- Fourier meets M\"{o}bius: fast subset convolution
- Faster Algorithms on Branch and Clique Decompositions
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Parallel Algorithms with Optimal Speedup for Bounded Treewidth
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
- Optimal dynamic program for r-domination problems over tree decompositions
- Parameterized Approximation Schemes Using Graph Widths
- Parameterized Algorithms
- On the complexity of \(k\)-SAT
This page was built for publication: Structurally parameterized \(d\)-scattered set
