Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor
From MaRDI portal
Publication:5111882
DOI10.4230/LIPIcs.IPEC.2017.23zbMath1443.68133OpenAlexW2964190780MaRDI QIDQ5111882
Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna
Publication date: 27 May 2020
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8557/pdf/LIPIcs-IPEC-2017-23.pdf/
Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph minors (05C83) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Cites Work
- Unnamed Item
- Kernelization using structural parameters on sparse graph classes
- Linear connectivity forces large complete bipartite minors: an alternative approach
- Turing kernelization for finding long paths and cycles in restricted graph classes
- Graph minors. XVII: Taming a vortex
- Parameterized computational complexity of finding small-diameter subgraphs
- The circumference of a graph with no \(K_{3,t}\)-minor. II
- Turing kernelization for finding long paths in graph classes excluding a topological minor
- A completeness theory for polynomial (Turing) kernelization
- A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs
- 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
