Turing kernelization for finding long paths and cycles in restricted graph classes
From MaRDI portal
DOI10.1016/j.jcss.2016.10.008zbMath1356.68099arXiv1402.4718OpenAlexW1566722385MaRDI QIDQ730497
Publication date: 28 December 2016
Published in: Journal of Computer and System Sciences, Algorithms - ESA 2014 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1402.4718
Related Items (11)
On the kernelization of split graph problems ⋮ A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion ⋮ Kernelization of Two Path Searching Problems on Split Graphs ⋮ Approximate Turing Kernelization for Problems Parameterized by Treewidth ⋮ A polynomial Turing-kernel for weighted independent set in bull-free graphs ⋮ Turing kernelization for finding long paths in graph classes excluding a topological minor ⋮ Turing kernelization for finding long paths and cycles in restricted graph classes ⋮ Parameterized certificate dispersal and its variants ⋮ On some FPT problems without polynomial Turing compressions ⋮ Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor ⋮ A completeness theory for polynomial (Turing) kernelization
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Kernel bounds for path and cycle problems
- Lower bounds on kernelization
- Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
- Infeasibility of instance compression and succinct PCPs for NP
- Turing kernelization for finding long paths and cycles in restricted graph classes
- Some consequences of non-uniform conditions on uniform classes
- On problems without polynomial kernels
- Parameterized computational complexity of finding small-diameter subgraphs
- Long cycles in 3-connected graphs
- The circumference of a graph with no \(K_{3,t}\)-minor. II
- Pancyclicity and NP-completeness in planar graphs
- A completeness theory for polynomial (Turing) kernelization
- Parametrized complexity theory.
- Fast Witness Extraction Using a Decision Oracle
- A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs
- On the Kernelization Complexity of Colorful Motifs
- Kernel(s) for problems with no kernel
- Approximating Longest Cycles in Graphs with Bounded Degrees
- Kernelization: New Upper and Lower Bound Techniques
- Kernelization Lower Bounds by Cross-Composition
- Finding Highly Connected Subgraphs
- Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
- Parameterized certificate dispersal and its variants
This page was built for publication: Turing kernelization for finding long paths and cycles in restricted graph classes