Kernel bounds for path and cycle problems
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 5994533 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 751135 (Why is no real title available?)
- scientific article; zbMATH DE number 7053262 (Why is no real title available?)
- A Dynamic Programming Approach to Sequencing Problems
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Color-coding
- Cross-composition: a new technique for kernelization lower bounds
- Divide-and-Color
- Easy problems for tree-decomposable graphs
- Graph minors. XIII: The disjoint paths problem
- Graph theory
- Improved algorithms for path, matching, and packing problems
- Incompressibility through Colors and IDs
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
- Kernelization of packing problems
- Lower bounds for kernelizations and other preprocessing procedures
- Monadic second-order evaluations on tree-decomposable graphs
- Narrow sieves for parameterized paths and packings
- On problems without polynomial kernels
- On the complexity of approximating the independent set problem
- On the complexity of paths avoiding forbidden pairs
- On the parameterized complexity of multiple-interval graph problems
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Spanning Trees with Many Leaves
- The complexity ecology of parameters: An illustration using bounded max leaf number
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Tight bounds for linkages in planar graphs
Cited in
(25)- Packing arc-disjoint cycles in oriented graphs
- Packing cycles faster than Erdős-Pósa
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT
- Kernelization of two path searching problems on split graphs
- Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
- On Problems without Polynomial Kernels (Extended Abstract)
- Independent-set reconfiguration thresholds of hereditary graph classes
- Chordless Cycle Packing Is Fixed-Parameter Tractable
- Parameterized pre-coloring extension and list coloring problems
- Kernel bounds for disjoint cycles and disjoint paths
- Tractability, hardness, and kernelization lower bound for and/or graph solution
- Turing kernelization for finding long paths in graph classes excluding a topological minor
- On the parameterized complexity of edge-linked paths
- Solving problems on graphs of high rank-width
- Meta-kernelization using well-structured modulators
- The parameterized complexity of cycle packing: indifference is not an issue
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Kernel bounds for path and cycle problems
- Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
- Hans Bodlaender and the Theory of Kernelization Lower Bounds
- Kernelization of graph Hamiltonicity: proper \(H\)-graphs
- A completeness theory for polynomial (Turing) kernelization
- Kernelization of graph Hamiltonicity: proper \(H\)-graphs
- On the complexity of approximately matching a string to a directed graph
- Kernel bounds for structural parameterizations of pathwidth
This page was built for publication: Kernel bounds for path and cycle problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q392032)
