Grundy distinguishes treewidth from pathwidth
From MaRDI portal
Publication:5874480
Recommendations
Cites work
- scientific article; zbMATH DE number 5917571 (Why is no real title available?)
- scientific article; zbMATH DE number 2147949 (Why is no real title available?)
- scientific article; zbMATH DE number 7058467 (Why is no real title available?)
- A lower bound for approximating the Grundy number
- A note on first-fit coloring of interval graphs
- Algorithmic lower bounds for problems parameterized by clique-width
- Algorithmic meta-theorems for restrictions of treewidth
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
- Capacitated Domination and Covering: A Parameterized Perspective
- Clique-width. III: Hamiltonian cycle and the odd case of graph coloring
- Complexity and approximability of parameterized MAX-CSPs
- Constraint satisfaction with bounded treewidth revisited
- Counting linear extensions: parameterizations by treewidth
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
- First-fit coloring of bounded tolerance graphs
- First-fit coloring on interval graphs has performance ratio at least 5
- Inequalities for the Grundy chromatic number of graphs
- Known algorithms on graphs of bounded treewidth are probably optimal
- Linear time solvable optimization problems on graphs of bounded clique-width
- Matchings with lower quotas: algorithms and complexity
- Model checking lower bounds for simple graphs
- More bounds for the Grundy number of graphs
- New algorithms for maximum disjoint paths based on tree-likeness
- New results on directed edge dominating set
- On bounded-degree vertex deletion parameterized by treewidth
- On routing disjoint paths in bounded treewidth graphs
- On structural parameterizations of the bounded-degree vertex deletion problem
- On the Grundy number of graphs with few P₄'s
- On the complexity of restoring corrupted colorings
- On the complexity of some colorful problems parameterized by treewidth
- On the equality of the partial Grundy and upper ochromatic numbers of graphs
- On the parameterized complexity of multiple-interval graph problems
- On the parameterized complexity of spanning trees with small vertex covers
- On tractable cases of target set selection
- On-line and first fit colorings of graphs
- Parameterized (approximate) defective coloring
- Parameterized Algorithms for Modular-Width
- Parameterized algorithms
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Parameterized complexity of fair vertex evaluation problems
- Parameterized complexity of length-bounded cuts and multicuts
- Parameterized complexity of safe set
- Parameterized maximum path coloring
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Results on the Grundy chromatic number of graphs
- Satisfiability of acyclic and almost acyclic CNF formulas
- Some perfect coloring properties of graphs
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- Structurally parameterized \(d\)-scattered set
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- The Steiner forest problem revisited
- The complexity landscape of decompositional parameters for ILP
- The mixed Chinese postman problem parameterized by pathwidth and treedepth
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The parameterised complexity of computing the maximum modularity of a graph
- The parameterised complexity of list problems on graphs of bounded treewidth
- Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
- Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus
- Time-approximation trade-offs for inapproximable problems
- Tractable cases of the extended global cardinality constraint
- Tree-depth, subgraph coloring and homomorphism bounds
- Treewidth governs the complexity of target set selection
- Treewidth with a quantifier alternation revisited
- What makes equitable connected partition easy
Cited in
(8)- On the parameterized complexity of \textsc{Sparsest Cut} and \textsc{Small-Set Expansion} problems
- Grundy Distinguishes Treewidth from Pathwidth
- In)approximability of Maximum Minimal FVS
- Extended MSO model checking via small vertex integrity
- \(b\)-coloring parameterized by clique-width
- (In)approximability of maximum minimal FVS
- Exploring the gap between treedepth and vertex cover through vertex integrity
- Exploring the gap between treedepth and vertex cover through vertex integrity
This page was built for publication: Grundy distinguishes treewidth from pathwidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874480)
