Turing kernelization for finding long paths in graph classes excluding a topological minor
From MaRDI portal
Publication:2272596
DOI10.1007/s00453-019-00614-4zbMath1430.68219arXiv1707.01797OpenAlexW3046608358WikidataQ127411783 ScholiaQ127411783MaRDI QIDQ2272596
Marcin Wrochna, Marcin Pilipczuk, Bart M. P. Jansen
Publication date: 10 September 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1707.01797
Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion ⋮ Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space ⋮ Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower and upper bounds for long induced paths in 3-connected planar graphs
- Kernelization using structural parameters on sparse graph classes
- Sparsity. Graphs, structures, and algorithms
- A polynomial Turing-kernel for weighted independent set in bull-free graphs
- Linear connectivity forces large complete bipartite minors: an alternative approach
- Turing kernelization for finding long paths and cycles in restricted graph classes
- Graph minors. V. Excluding a planar graph
- Graph minors. X: Obstructions to tree-decomposition
- Graph minors. XVII: Taming a vortex
- Parameterized computational complexity of finding small-diameter subgraphs
- Long cycles in 3-connected graphs
- On the excluded minor structure theorem for graphs of large tree-width
- The circumference of a graph with no \(K_{3,t}\)-minor. II
- A completeness theory for polynomial (Turing) kernelization
- On the Kernelization Complexity of Colorful Motifs
- Kernel(s) for problems with no kernel
- Approximating Longest Cycles in Graphs with Bounded Degrees
- Exploring the Complexity of Layout Parameters in Tournaments and Semicomplete Digraphs
- Kernelization Lower Bounds by Cross-Composition
- Finding Highly Connected Subgraphs
- Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
- Minimum bisection is fixed parameter tractable
- Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
- Some Theorems on Abstract Graphs
- Parameterized certificate dispersal and its variants
