scientific article; zbMATH DE number 5485524
From MaRDI portal
Publication:3549693
zbMATH Open1231.68133MaRDI QIDQ3549693FDOQ3549693
Rahul Santhanam, Lance Fortnow
Publication date: 5 January 2009
Title of this publication is not available (Why is that?)
Cited In (38)
- Facility location problems: a parameterized view
- Lower bounds for kernelizations and other preprocessing procedures
- Kernelization: new upper and lower bound techniques
- On the Kernelization Complexity of Colorful Motifs
- What’s Next? Future Directions in Parameterized Complexity
- Collapsing and separating completeness notions under average-case and worst-case hypotheses
- Quadratic kernelization for convex recoloring of trees
- Parameterized Complexity of Firefighting Revisited
- Infeasibility of instance compression and succinct PCPs for NP
- On Cutwidth Parameterized by Vertex Cover
- On problems without polynomial kernels
- Depth Reduction for Composites
- Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
- Polynomial Turing compressions for some graph problems parameterized by modular-width
- On the small cycle transversal of planar graphs
- Two edge modification problems without polynomial kernels
- Linear kernelizations for restricted 3-Hitting Set problems
- Kernelization – Preprocessing with a Guarantee
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the Hardness of Losing Width
- Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
- Parameterized complexity of firefighting
- Fréchet distance between a line and avatar point set
- Lower bounds on kernelization
- Guarantees and limits of preprocessing in constraint satisfaction and reasoning
- What Is Known About Vertex Cover Kernelization?
- Towards Non-Black-Box Separations of Public Key Encryption and One Way Function
- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
- The kernelization complexity of connected domination in graphs with (no) small cycles
- Probabilistically checkable arguments for all NP
- A linear kernel for the complementary maximal strip recovery problem
- Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
- Backdoors to Satisfaction
- A multi-parameter analysis of hard problems on deterministic finite automata
- Lower Bounds for Kernelizations and Other Preprocessing Procedures
- A Problem Kernelization for Graph Packing
- Hitting forbidden minors: approximation and kernelization
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3549693)
