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

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

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)

Cites Work

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

Cited In (6)

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

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)