Twin-width and polynomial kernels
From MaRDI portal
Publication:2093574
Recommendations
- Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
- Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
- Tight kernel bounds for problems on graphs with small degeneracy
- Polynomial kernels and wideness properties of nowhere dense graph classes
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
Cites work
- A simple linear time algorithm for cograph recognition
- Automata, Languages and Programming
- Bidimensionality and kernels
- Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
- Deterministic parameterized connected vertex cover
- Dominating set is fixed parameter tractable in claw-free graphs
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Domination in permutation graphs
- Domination problems in nowhere-dense classes of graphs
- Dynamic Programming and Fast Matrix Multiplication
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Exploiting c-Closure in Kernelization Algorithms for Graph Problems
- FPT algorithms for domination in sparse graphs and beyond
- Fundamentals of parameterized complexity
- Kernelization and Sparseness: the case of Dominating Set
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
- Kernelization lower bounds through colors and IDs
- Kernelization using structural parameters on sparse graph classes
- Kernels for (connected) dominating set on graphs with excluded topological minors
- Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- On problems without polynomial kernels
- Parameterized algorithms
- Parameterized Complexity for Domination Problems on Degenerate Graphs
- Parameterized domination in circle graphs
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Planar Formulae and Their Uses
- Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
- Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
- Polynomial-time data reduction for dominating set
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- Some simplified NP-complete graph problems
- Sparsity. Graphs, structures, and algorithms
- Strong computational lower bounds via parameterized complexity
- Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
- Tight kernel bounds for problems on graphs with small degeneracy
- Twin-width. I: Tractable FO model checking
- Unit disk graphs
- Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
Cited in
(23)- Bounds for the twin-width of graphs
- Twin-width can be exponential in treewidth
- Graphs of bounded twin-width are quasi-polynomially -bounded
- Neighbourhood complexity of graphs of bounded twin-width
- Bounds on the Twin-Width of Product Graphs
- Twin-width and polynomial kernels
- Twin-width and polynomial kernels
- Twin-width. III: Max independent set, min dominating set, and coloring
- Twin-width of random graphs
- Twin-width of graphs with tree-structured decompositions
- A polynomial Ramsey statement for bounded VC-dimension
- Isomorphism for tournaments of small twin width
- Computing twin-width parameterized by the feedback edge number
- Computing twin-width parameterized by the feedback edge number and vertex integrity
- PACE solver description: Touiouidth
- PACE solver description: exact (GUTHMI) and heuristic (GUTHM)
- Sparse graphs of twin-width 2 have bounded tree-width
- Structural parameterization of cluster deletion
- Twin-width of subdivisions of multigraphs
- Improved bounds for twin-width parameter variants with algorithmic applications to counting graph colorings
- Equitable connected partition and structural parameters revisited: N-fold beats Lenstra
- Advances in algorithmic meta theorems (invited paper)
- Twin-width one
This page was built for publication: Twin-width and polynomial kernels
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2093574)
