Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter (Q372970): 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/s00224-012-9393-4
+Normal rank
@@ Property / OpenAlex ID @@
+W3122973673
@@ Property / OpenAlex ID: W3122973673 / rank @@
+Normal rank
@@ Property / cites work @@
+Crown structures for vertex cover kernelization
@@ Property / cites work: Crown structures for vertex cover kernelization / rank @@
+Normal rank
@@ Property / cites work @@
+A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
+Normal rank
@@ Property / cites work @@
+On problems without polynomial kernels
@@ Property / cites work: On problems without polynomial kernels / rank @@
+Normal rank
@@ Property / cites work @@
+Q3113681
@@ Property / cites work: Q3113681 / rank @@
+Normal rank
@@ Property / cites work @@
+Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
+Normal rank
@@ Property / cites work @@
+Nondeterminism within $P^ *  $
@@ Property / cites work: Nondeterminism within $P^ * $ / rank @@
+Normal rank
@@ Property / cites work @@
+Parameterized complexity of vertex colouring
@@ Property / cites work: Parameterized complexity of vertex colouring / rank @@
+Normal rank
@@ Property / cites work @@
+Vertex Cover: Further Observations and Further Improvements
+Normal rank
@@ Property / cites work @@
+Improved upper bounds for vertex cover
@@ Property / cites work: Improved upper bounds for vertex cover / rank @@
+Normal rank
@@ Property / cites work @@
+Crown reductions for the minimum weighted vertex cover problem
+Normal rank
@@ Property / cites work @@
+Graph-Theoretic Concepts in Computer Science
@@ Property / cites work: Graph-Theoretic Concepts in Computer Science / rank @@
+Normal rank
@@ Property / cites work @@
+On the Hardness of Losing Width
@@ Property / cites work: On the Hardness of Losing Width / rank @@
+Normal rank
@@ Property / cites work @@
+Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
+Normal rank
@@ Property / cites work @@
+Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
+Normal rank
@@ Property / cites work @@
+Kernels for the Vertex Cover Problem on the Preferred Attachment Model
+Normal rank
@@ Property / cites work @@
+Incompressibility through Colors and IDs
@@ Property / cites work: Incompressibility through Colors and IDs / rank @@
+Normal rank
@@ Property / cites work @@
+Q4263467
@@ Property / cites work: Q4263467 / rank @@
+Normal rank
@@ Property / cites work @@
+Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
+Normal rank
@@ Property / cites work @@
+The complexity ecology of parameters: An illustration using bounded max leaf number
+Normal rank
@@ Property / cites work @@
+Graph Layout Problems Parameterized by Vertex Cover
+Normal rank
@@ Property / cites work @@
+Infeasibility of instance compression and succinct PCPs for NP
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Spanning trees with many leaves in cubic graphs
@@ Property / cites work: Spanning trees with many leaves in cubic graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Vertex cover problem parameterized above and below tight bounds
+Normal rank
@@ Property / cites work @@
+Q3113682
@@ Property / cites work: Q3113682 / rank @@
+Normal rank
@@ Property / cites work @@
+On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal
+Normal rank
@@ Property / cites work @@
+Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
+Normal rank
@@ Property / cites work @@
+Isomorphism for Graphs of Bounded Feedback Vertex Set Number
+Normal rank
@@ Property / cites work @@
+The complexity of König subgraph problems and above-guarantee vertex cover
+Normal rank
@@ Property / cites work @@
+Vertex packings: Structural properties and algorithms
+Normal rank
@@ Property / cites work @@
+Q5710169
@@ Property / cites work: Q5710169 / rank @@
+Normal rank
@@ Property / cites work @@
+Reflections on Multivariate Algorithmics and Problem Parameterization
+Normal rank
@@ Property / cites work @@
+On efficient fixed-parameter algorithms for weighted vertex cover
+Normal rank
@@ Property / cites work @@
+Paths, Flowers and Vertex Cover
@@ Property / cites work: Paths, Flowers and Vertex Cover / rank @@
+Normal rank
@@ Property / cites work @@
+Almost 2-SAT is fixed-parameter tractable
@@ Property / cites work: Almost 2-SAT is fixed-parameter tractable / rank @@
+Normal rank
@@ Property / cites work @@
+Combinatorial optimization. Polyhedra and efficiency (3 volumes)
+Normal rank
@@ Property / cites work @@
+A kernel of order \(2k - c\) for Vertex Cover
@@ Property / cites work: A kernel of order \(2k - c\) for Vertex Cover / rank @@
+Normal rank
@@ Property / cites work @@
+Two-Layer Planarization Parameterized by Feedback Edge Set
+Normal rank
@@ Property / cites work @@
+Some consequences of non-uniform conditions on uniform classes
+Normal rank
@@ Property / cites work @@
+The structure and maximum number of maximum independent sets in trees
+Normal rank
@@ Property / DBLP publication ID @@
+journals/mst/JansenB13
@@ Property / DBLP publication ID: journals/mst/JansenB13 / rank @@
+Normal rank