Towards exact structural thresholds for parameterized complexity
From MaRDI portal
Cites work
- A partial k-arboretum of graphs with bounded treewidth
- A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank
- Algorithmic meta-theorems for restrictions of treewidth
- Anti-factor is FPT parameterized by treewidth and list size (but counting is hard)
- Branch-depth: generalizing tree-depth of graphs
- Computing the chromatic number using graph decompositions via matrix rank
- Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
- Elimination distances, blocking sets, and kernels for Vertex Cover
- Fast Hamiltonicity checking via bases of perfect matchings
- Faster parameterized algorithms using linear programming
- Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
- Fine-grained parameterized complexity analysis of graph coloring problems
- Finer tight bounds for coloring on clique-width
- Fixed-parameter tractable distances to sparse graph classes
- FO-Definability of Shrub-Depth
- Graph isomorphism parameterized by elimination distance to bounded degree
- scientific article; zbMATH DE number 7228418 (Why is no real title available?)
- scientific article; zbMATH DE number 7029306 (Why is no real title available?)
- scientific article; zbMATH DE number 7650941 (Why is no real title available?)
- scientific article; zbMATH DE number 7651213 (Why is no real title available?)
- scientific article; zbMATH DE number 7803599 (Why is no real title available?)
- Known algorithms on graphs of bounded treewidth are probably optimal
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Meta-kernelization using well-structured modulators
- Model counting for CNF formulas of bounded modular treewidth
- New algorithms for mixed dominating set
- Obstructions for bounded shrub-depth and rank-depth
- On problems as hard as CNF-SAT
- On the complexity of k-SAT
- On the equivalence among problems of bounded width
- Optimal dynamic program for r-domination problems over tree decompositions
- Parameterized algorithms
- Parameterized Algorithms for Modular-Width
- Parameterized compilation lower bounds for restricted CNF-formulas
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Solving problems on graphs of high rank-width
- Sparsity. Graphs, structures, and algorithms
- Structural parameterizations with modulator oblivion
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- Structurally parameterized \(d\)-scattered set
- The fine-grained complexity of graph homomorphism parameterized by clique-width
- Tight bounds for counting colorings and connected edge sets parameterized by cutwidth
- Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus
- Tree-depth and vertex-minors
- Upper bounds to the clique width of graphs
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- Vertex deletion parameterized by elimination distance and even less
- Which problems have strongly exponential complexity?
Cited in
(3)
This page was built for publication: Towards exact structural thresholds for parameterized complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6968995)
