On the partial vertex cover problem in bipartite graphs -- a parameterized perspective

DOI10.1007/s00224-023-10152-wOpenAlexW4389209950MaRDI QIDQ6151150

No author found.

Publication date: 9 February 2024

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-023-10152-w

zbMATH Keywords

bipartite graphfixed parameter tractabilityexponential algorithmpartial vertex coverweighted partial vertex cover

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A unified approach to approximating partial covering problems
• Implicit branching and parameterized partial cover problems
• On the hardness of approximating minimum vertex cover
• Computing small partial coverings
• Parameterized circuit complexity and the \(W\) hierarchy
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• 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 minimum generalized vertex cover problem
• 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
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Reducibility among Combinatorial Problems
• Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
• On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite 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
• Pseudorandom sets in Grassmann graph have near-perfect expansion

This page was built for publication: On the partial vertex cover problem in bipartite graphs -- a parameterized perspective