Turing kernelization for finding long paths and cycles in restricted graph classes
type: Item
instance of: scholarly article
title: Turing kernelization for finding long paths and cycles in restricted graph classes
title: Turing Kernelization for Finding Long Paths and Cycles in Restricted Graph Classes
zbMATH Open document ID: 1356.68099
zbMATH Open document ID: 1425.68144
DOI: 10.1007/978-3-662-44777-2_48
DOI: 10.1016/J.JCSS.2016.10.008
author: Bart M. P. Jansen
published in: Journal of Computer and System Sciences
published in: Algorithms - ESA 2014
publication date: 2016-12-28T00:00:00Z
publication date: 2014-10-08T00:00:00Z
full work available at URL: https://arxiv.org/abs/1402.4718
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 6668744
zbMATH DE Number: 6352781
zbMATH Keywords: parameterized complexity
zbMATH Keywords: Turing kernelization
zbMATH Keywords: \(k\)-Path
zbMATH Keywords: preprocessing
describes a project that uses: Algorithm 447
MaRDI profile type: Publication
OpenAlex ID: W1566722385
OpenAlex ID: W2620774572
arXiv ID: 1402.4718
cites work: On the Kernelization Complexity of Colorful Motifs
cites work: Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
cites work: Kernel(s) for problems with no kernel
cites work: Fast Witness Extraction Using a Decision Oracle
cites work: Kernelization: New Upper and Lower Bound Techniques
cites work: On problems without polynomial kernels
cites work: Kernel bounds for path and cycle problems
cites work: Kernelization Lower Bounds by Cross-Composition
cites work: Approximating Longest Cycles in Graphs with Bounded Degrees
cites work: Long cycles in 3-connected graphs
cites work: The circumference of a graph with no \(K_{3,t}\)-minor. II
cites work: Parameterized Algorithms
cites work: Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
cites work: Q3577833
cites work: Fundamentals of parameterized complexity
cites work: Q3798235
cites work: Parametrized complexity theory.
cites work: Infeasibility of instance compression and succinct PCPs for NP
cites work: Parameterized certificate dispersal and its variants
cites work: Q4472293
cites work: A completeness theory for polynomial (Turing) kernelization
cites work: Finding Highly Connected Subgraphs
cites work: Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
cites work: Q5275384
cites work: Pancyclicity and NP-completeness in planar graphs
cites work: Lower bounds on kernelization
cites work: Parameterized computational complexity of finding small-diameter subgraphs
cites work: A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs
cites work: Q5524326
cites work: Some consequences of non-uniform conditions on uniform classes
description: scientific article; zbMATH DE number 6352781
alternative label: Turing Kernelization for Finding Long Paths and Cycles in Restricted Graph Classes