Grundy Distinguishes Treewidth from Pathwidth
From MaRDI portal
Publication:5096586
DOI10.1137/20M1385779MaRDI QIDQ5096586FDOQ5096586
Authors: Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi 
Publication date: 18 August 2022
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2008.07425
Recommendations
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Some perfect coloring properties of graphs
- A partial k-arboretum of graphs with bounded treewidth
- Algorithmic meta-theorems for restrictions of treewidth
- Linear time solvable optimization problems on graphs of bounded clique-width
- Tractable cases of the extended global cardinality constraint
- Tree-depth, subgraph coloring and homomorphism bounds
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Integer Programming with a Fixed Number of Variables
- Minkowski's Convex Body Theorem and Integer Programming
- Treewidth governs the complexity of target set selection
- Parameterized algorithms
- Satisfiability of acyclic and almost acyclic CNF formulas
- An improved bound for first-fit on posets without two long incomparable chains
- Constraint satisfaction with bounded treewidth revisited
- Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- Results on the Grundy chromatic number of graphs
- On bounded-degree vertex deletion parameterized by treewidth
- On the parameterized complexity of multiple-interval graph problems
- An application of simultaneous diophantine approximation in combinatorial optimization
- Parameterized Algorithms for Modular-Width
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- On-line and first fit colorings of graphs
- Algorithmic lower bounds for problems parameterized by clique-width
- No small nondeterministic read-once branching programs for CNFs of bounded treewidth
- Inequalities for the Grundy chromatic number of graphs
- Title not available (Why is that?)
- A lower bound for approximating the Grundy number
- Primal-dual approximation algorithms for integral flow and multicut in trees
- On the Grundy and \(b\)-chromatic numbers of a graph
- The mixed Chinese postman problem parameterized by pathwidth and treedepth
- The parameterised complexity of list problems on graphs of bounded treewidth
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- On the complexity of some colorful problems parameterized by treewidth
- Capacitated Domination and Covering: A Parameterized Perspective
- Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
- Parameterized maximum path coloring
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Model checking lower bounds for simple graphs
- On the equality of the partial Grundy and upper ochromatic numbers of graphs
- Complexity and approximability of parameterized MAX-CSPs
- What makes equitable connected partition easy
- First-fit coloring on interval graphs has performance ratio at least 5
- A note on first-fit coloring of interval graphs
- More bounds for the Grundy number of graphs
- On tractable cases of target set selection
- First-fit coloring of bounded tolerance graphs
- Parameterized complexity of \((A,\ell)\)-path packing
- Title not available (Why is that?)
- On the Grundy number of graphs with few \(P_4\)'s
- On the parameterized complexity of spanning trees with small vertex covers
- Counting linear extensions: parameterizations by treewidth
- The parameterised complexity of computing the maximum modularity of a graph
- Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus
- On structural parameterizations of the bounded-degree vertex deletion problem
- Known algorithms on graphs of bounded treewidth are probably optimal
- Clique-width. III: Hamiltonian cycle and the odd case of graph coloring
- Notes on complexity of packing coloring
- The Steiner forest problem revisited
- Parameterized complexity of length-bounded cuts and multicuts
- Structurally parameterized \(d\)-scattered set
- Parameterized orientable deletion
- Time-approximation trade-offs for inapproximable problems
- Parameterized complexity of fair vertex evaluation problems
- Matchings with lower quotas: algorithms and complexity
- The complexity landscape of decompositional parameters for ILP
- New algorithms for maximum disjoint paths based on tree-likeness
- On routing disjoint paths in bounded treewidth graphs
- Metric dimension parameterized by treewidth
- Parameterized (approximate) defective coloring
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
- Length-bounded cuts: proper interval graphs and structural parameters
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- New results on directed edge dominating set
- Parameterized complexity of safe set
- Treewidth with a quantifier alternation revisited
- On the complexity of restoring corrupted colorings
Cited In (1)
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 Q5096586)
