scientific article
From MaRDI portal
Publication:3549693
zbMath1231.68133MaRDI QIDQ3549693
Rahul Santhanam, Lance J. Fortnow
Publication date: 5 January 2009
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (36)
Parameterized Complexity of Firefighting Revisited ⋮ On the Hardness of Losing Width ⋮ On Cutwidth Parameterized by Vertex Cover ⋮ Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds ⋮ Kernelization – Preprocessing with a Guarantee ⋮ Backdoors to Satisfaction ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Towards Non-Black-Box Separations of Public Key Encryption and One Way Function ⋮ Infeasibility of instance compression and succinct PCPs for NP ⋮ What Is Known About Vertex Cover Kernelization? ⋮ Quadratic kernelization for convex recoloring of trees ⋮ Lower bounds on kernelization ⋮ Guarantees and limits of preprocessing in constraint satisfaction and reasoning ⋮ The kernelization complexity of connected domination in graphs with (no) small cycles ⋮ Parameterized complexity of firefighting ⋮ A linear kernel for the complementary maximal strip recovery problem ⋮ Depth Reduction for Composites ⋮ Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number ⋮ Lower Bounds for Kernelizations and Other Preprocessing Procedures ⋮ Collapsing and separating completeness notions under average-case and worst-case hypotheses ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ Lower bounds for kernelizations and other preprocessing procedures ⋮ On the small cycle transversal of planar graphs ⋮ A Problem Kernelization for Graph Packing ⋮ Facility location problems: a parameterized view ⋮ Linear kernelizations for restricted 3-Hitting Set problems ⋮ Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ On the Kernelization Complexity of Colorful Motifs ⋮ On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems ⋮ Fréchet distance between a line and avatar point set ⋮ On problems without polynomial kernels ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ Two Edge Modification Problems without Polynomial Kernels ⋮ Unnamed Item ⋮ Unnamed Item
This page was built for publication: