Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
From MaRDI portal
Publication:2119402
DOI10.1016/j.jcss.2021.12.003zbMath1483.68258arXiv2004.08818OpenAlexW4226052445MaRDI QIDQ2119402
Bart M. P. Jansen, Jari J. H. de Kroon
Publication date: 29 March 2022
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2004.08818
Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (1)
Cites Work
- Unnamed Item
- Fundamentals of parameterized complexity
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Two-layer planarization parameterized by feedback edge set
- Parameterized complexity of vertex deletion into perfect graph classes
- Data reduction for graph coloring problems
- Sparsity. Graphs, structures, and algorithms
- On cutwidth parameterized by vertex cover
- The strong perfect graph theorem
- Recognizing graphs without asteroidal triples
- The node-deletion problem for hereditary properties is NP-complete
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- Optimal data reduction for graph coloring using low-degree polynomials
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Polynomial kernelization for removing induced claws and diamonds
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
- (Meta) Kernelization
- Uniform Kernelization Complexity of Hitting Forbidden Minors
- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
- Wheel-Free Deletion Is W[2-Hard]
- Graph Classes: A Survey
- Approximation and Kernelization for Chordal Vertex Deletion
- Kernelization
- Compression via Matroids
- Kernelization Lower Bounds by Cross-Composition
- A Polynomial Kernel for Diamond-Free Editing
- Interval Vertex Deletion Admits a Polynomial Kernel
- Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs
- Parameterized Algorithms
- Transitiv orientierbare Graphen
- Partially Ordered Sets
- Binomial Coefficients Modulo a Prime
- Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
This page was built for publication: Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
