Safe Approximation and Its Relation to Kernelization (Q2891346): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/978-3-642-28050-4_14
+Normal rank
@@ Property / OpenAlex ID @@
+W1963195391
@@ Property / OpenAlex ID: W1963195391 / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial-time data reduction for dominating set
@@ Property / cites work: Polynomial-time data reduction for dominating set / rank @@
+Normal rank
@@ Property / cites work @@
+A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for NP-complete problems on planar graphs
+Normal rank
@@ Property / cites work @@
+Q3337223
@@ Property / cites work: Q3337223 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
+Normal rank
@@ Property / cites work @@
+A Linear Kernel for Planar Feedback Vertex Set
@@ Property / cites work: A Linear Kernel for Planar Feedback Vertex Set / rank @@
+Normal rank
@@ Property / cites work @@
+Nondeterminism within $P^ *  $
@@ Property / cites work: Nondeterminism within $P^ * $ / rank @@
+Normal rank
@@ Property / cites work @@
+On fixed-parameter tractability and approximability of NP optimization problems
+Normal rank
@@ Property / cites work @@
+The complexity of polynomial-time approximation
@@ Property / cites work: The complexity of polynomial-time approximation / rank @@
+Normal rank
@@ Property / cites work @@
+On the efficiency of polynomial time approximation schemes
+Normal rank
@@ Property / cites work @@
+Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
+Normal rank
@@ Property / cites work @@
+Strong computational lower bounds via parameterized complexity
+Normal rank
@@ Property / cites work @@
+Polynomial time approximation schemes and parameterized complexity
+Normal rank
@@ Property / cites work @@
+Vertex Cover: Further Observations and Further Improvements
+Normal rank
@@ Property / cites work @@
+Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for combinatorial problems
+Normal rank
@@ Property / cites work @@
+Q4910736
@@ Property / cites work: Q4910736 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation properties of NP minimization classes
+Normal rank
@@ Property / cites work @@
+Algorithms – ESA 2005
@@ Property / cites work: Algorithms – ESA 2005 / rank @@
+Normal rank
@@ Property / cites work @@
+Vertex packings: Structural properties and algorithms
+Normal rank
@@ Property / cites work @@
+Optimization, approximation, and complexity classes
+Normal rank
@@ Property / cites work @@
+Depth-first search and the vertex cover problem
@@ Property / cites work: Depth-first search and the vertex cover problem / rank @@
+Normal rank
@@ Property / cites work @@
+A 4             <i>k</i>             <sup>2</sup>             kernel for feedback vertex set
+Normal rank