Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs

DOI10.1007/978-3-030-48966-3_30MaRDI QIDQ5041208zbMATH OpenOpenAlexFDO

Authors

Publication date 13 October 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.12011

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Recommendations

• On the partial vertex cover problem in bipartite graphs -- a parameterized perspective
• On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
• scientific article; zbMATH DE number 2080245
• Parameterized approximation algorithms for weighted vertex cover
• Parameterized complexity of Vertex Cover variants

Cites work

• A better approximation ratio for the vertex cover problem
• A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
• A unified approach to approximating partial covering problems
• Algorithms and Data Structures
• Approximation algorithms for partial covering problems
• Approximation of Partial Capacitated Vertex Cover
• Computing small partial coverings
• scientific article; zbMATH DE number 6515828 (Why is no real title available?)
• scientific article; zbMATH DE number 1342117 (Why is no real title available?)
• scientific article; zbMATH DE number 1182766 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• Implicit branching and parameterized partial cover problems
• Improved approximation of maximum vertex coverage problem on bipartite graphs
• Improved Upper Bounds for Partial Vertex Cover
• Intuitive Algorithms and t-Vertex Cover
• On non-optimally expanding sets in Grassmann graphs
• On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs
• On the hardness of approximating minimum vertex cover
• Optimization, approximation, and complexity classes
• Parameterized algorithms
• Partial vertex cover and budgeted maximum coverage in bipartite graphs
• Partial vs. Complete Domination: t-Dominating Set
• Reducibility among combinatorial problems
• The approximability of partial vertex covers in trees
• The budgeted maximum coverage problem
• The maximum vertex coverage problem on bipartite graphs
• Using homogeneous weights for approximating the partial cover problem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(4)

• On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs
• On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
• On the partial vertex cover problem in bipartite graphs -- a parameterized perspective
• Implicit branching and parameterized partial cover problems

This page was built for publication: Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5041208)