Structurally parameterized d-scattered set

DOI10.1016/J.DAM.2020.03.052zbMATH Open1479.05081OpenAlexW3015605341MaRDI QIDQ2064293FDOQ2064293

Authors Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos

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

zbMATH Keywords

independencetreewidthSETHdistance parameter

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12)

Recommendations

• Structurally parameterized \(d\)-scattered set
• Improved (In-)Approximability Bounds for d-Scattered Set
• H-free graphs, independent sets, and subexponential-time algorithms
• Scattered packings of cycles
• Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs

Cites work

• scientific article; zbMATH DE number 6783430 (Why is no real title available?)
• Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Approximation algorithm for the distance-3 independent set problem on cubic graphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Distance-\(d\) independent set problems for bipartite and chordal graphs
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Faster algorithms on branch and clique decompositions
• Fourier meets M\"{o}bius: fast subset convolution
• Fundamentals of parameterized complexity
• Independent sets with domination constraints
• Known algorithms on graphs of bounded treewidth are probably optimal
• Mixed searching and proper-path-width
• On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
• On the complexity of \(k\)-SAT
• Optimal dynamic program for \(r\)-domination problems over tree decompositions
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Parameterized Approximation Schemes Using Graph Widths
• Parameterized algorithms
• Parametrized complexity theory.
• Scheduling of pipelined operator graphs
• Structural parameters, tight bounds, and approximation for \((k, r)\)-center
• The algorithmic theory of treewidth
• Tree-depth, subgraph coloring and homomorphism bounds
• Treewidth. Computations and approximations
• Treewidth: Characterizations, Applications, and Computations
• Upper bounds to the clique width of graphs
• Which problems have strongly exponential complexity?

Cited in

(6)

• On the complexity of distance-\(d\) independent set reconfiguration
• Structurally parameterized \(d\)-scattered set
• Improved (In-)Approximability Bounds for d-Scattered Set
• On the tree-depth and tree-width in heterogeneous random graphs
• On the complexity of distance-\(d\) independent set reconfiguration
• On graphs coverable by \({k}\) shortest paths

This page was built for publication: Structurally parameterized \(d\)-scattered set

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