Kernel Bounds for Path and Cycle Problems

DOI10.1007/978-3-642-28050-4_12zbMath1352.68092arXiv1106.4141OpenAlexW2568069351WikidataQ59567543 ScholiaQ59567543MaRDI QIDQ2891344

Stefan Kratsch, Bart M. P. Jansen, Hans L. Bodlaender

Publication date: 15 June 2012

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1106.4141

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38)

Related Items (5)

New Limits to Classical and Quantum Instance Compression ⋮ Kernelization using structural parameters on sparse graph classes ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ Solving problems on graphs of high rank-width ⋮ Complexity of the path avoiding forbidden pairs problem revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds for kernelizations and other preprocessing procedures
• Infeasibility of instance compression and succinct PCPs for NP
• The complexity ecology of parameters: An illustration using bounded max leaf number
• On the parameterized complexity of multiple-interval graph problems
• On problems without polynomial kernels
• Graph minors. XIII: The disjoint paths problem
• Narrow sieves for parameterized paths and packings
• Parametrized complexity theory.
• Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
• Spanning Trees with Many Leaves
• Divide-and-Color
• Incompressibility through Colors and IDs
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Color-coding
• Research in Computational Molecular Biology

This page was built for publication: Kernel Bounds for Path and Cycle Problems