Crown reductions for the minimum weighted vertex cover problem
From MaRDI portal
Publication:2473030
DOI10.1016/j.dam.2007.03.026zbMath1132.68071OpenAlexW2077654620MaRDI QIDQ2473030
Janka Chlebíková, Miroslav Chlebík
Publication date: 26 February 2008
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2007.03.026
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)
Related Items
Linear kernels for separating a graph into components of bounded size, Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems, Maximum Minimal Vertex Cover Parameterized by Vertex Cover, A Multivariate Approach for Weighted FPT Algorithms, \(d\)-transversals of stable sets and vertex covers in weighted bipartite graphs, Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey, Parameterized Power Vertex Cover, Critical sets, crowns and local maximum independent sets, Polynomial kernels for weighted problems, On a generalization of Nemhauser and Trotter's local optimization theorem, A multivariate framework for weighted FPT algorithms, Critical and maximum independent sets of a graph, Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter, Maximum Minimal Vertex Cover Parameterized by Vertex Cover, Kernelization for feedback vertex set via elimination distance to a forest, Data Reduction for Maximum Matching on Real-World Graphs, Kernelization for feedback vertex set via elimination distance to a forest, On bounded block decomposition problems for under-specified systems of equations, A kernel of order \(2k-c\log k\) for vertex cover, Lower bounds on kernelization, A generalization of Nemhauser and Trotter's local optimization theorem, Blockers for the stability number and the chromatic number, Exploiting c-Closure in Kernelization Algorithms for Graph Problems, A kernel of order \(2k - c\) for Vertex Cover, Improved upper bounds for vertex cover, Kernels for packing and covering problems, Connection between conjunctive capacity and structural properties of graphs, Smaller Parameters for Vertex Cover Kernelization, The union of minimal hitting sets: parameterized combinatorial bounds and counting, On sparsification for computing treewidth
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover
- Matching theory
- On approximation properties of the independent set problem for low degree graphs
- König-Egerváry graphs, 2-bicritical graphs and fractional matchings
- On the number of vertices belonging to all maximum stable sets of a graph
- Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
- Pseudo-Hamiltonian-connected graphs
- Vertex Cover: Further Observations and Further Improvements
- Minimum node covers and 2-bicritical graphs
- Node-weighted graphs having the König-Egerváry property
- The importance of being biased
- A new approach to the maximum-flow problem
- Vertices Belonging to All or to No Maximum Stable Sets of a Graph
- Vertex packings: Structural properties and algorithms
- On the integer-valued variables in the linear vertex packing problem
- Regularisable Graphs
- Nondeterminism within $P^ * $
- On efficient fixed-parameter algorithms for weighted vertex cover
- On Representatives of Subsets
- Properties of vertex packing and independence system polyhedra
- Parameterized and Exact Computation
- Parameterized and Exact Computation
- Parameterized and Exact Computation
- Algorithm Theory - SWAT 2004
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
- Algorithms and Data Structures
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
