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 RevisitedOn the Hardness of Losing WidthOn Cutwidth Parameterized by Vertex CoverCrossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower BoundsKernelization – Preprocessing with a GuaranteeBackdoors to SatisfactionWhat’s Next? Future Directions in Parameterized ComplexityTowards Non-Black-Box Separations of Public Key Encryption and One Way FunctionInfeasibility of instance compression and succinct PCPs for NPWhat Is Known About Vertex Cover Kernelization?Quadratic kernelization for convex recoloring of treesLower bounds on kernelizationGuarantees and limits of preprocessing in constraint satisfaction and reasoningThe kernelization complexity of connected domination in graphs with (no) small cyclesParameterized complexity of firefightingA linear kernel for the complementary maximal strip recovery problemDepth Reduction for CompositesAlgorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover numberLower Bounds for Kernelizations and Other Preprocessing ProceduresCollapsing and separating completeness notions under average-case and worst-case hypothesesA multi-parameter analysis of hard problems on deterministic finite automataLower bounds for kernelizations and other preprocessing proceduresOn the small cycle transversal of planar graphsA Problem Kernelization for Graph PackingFacility location problems: a parameterized viewLinear kernelizations for restricted 3-Hitting Set problemsKernelization Hardness of Connectivity Problems in d-Degenerate GraphsHitting Forbidden Minors: Approximation and KernelizationOn the Kernelization Complexity of Colorful MotifsOn the (Non-)existence of Polynomial Kernels for P l -free Edge Modification ProblemsFréchet distance between a line and avatar point setOn problems without polynomial kernelsKernelization: New Upper and Lower Bound TechniquesTwo Edge Modification Problems without Polynomial KernelsUnnamed ItemUnnamed Item




This page was built for publication: