On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
DOI10.7155/jgaa.00584zbMath1490.68123arXiv2104.11215OpenAlexW3152890216MaRDI QIDQ5084707
No author found.
Publication date: 28 June 2022
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2104.11215
Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Signed and weighted graphs (05C22) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (1)
Cites Work
- A unified approach to approximating partial covering problems
- Implicit branching and parameterized partial cover problems
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- On the hardness of approximating minimum vertex cover
- Computing small partial coverings
- Optimization, approximation, and complexity classes
- The budgeted maximum coverage problem
- Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
- A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
- The maximum vertex coverage problem on bipartite graphs
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Using Homogeneous Weights for Approximating the Partial Cover Problem
- Improved Approximation of Maximum Vertex Coverage Problem on Bipartite Graphs
- The Approximability of Partial Vertex Covers in Trees
- On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs
- Approximation algorithms for partial covering problems
- Reducibility among Combinatorial Problems
- Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
- On non-optimally expanding sets in Grassmann graphs
- Improved Upper Bounds for Partial Vertex Cover
- Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs
- Algorithms and Data Structures
- Partial vs. Complete Domination: t-Dominating Set
- Intuitive Algorithms and t-Vertex Cover
- Parameterized Algorithms
- Approximation of Partial Capacitated Vertex Cover
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
