Improved Upper Bounds for Partial Vertex Cover

No abstract is available for this paper.

• Publication year

  2008

• Venue

  International Workshop on Graph-Theoretic Concepts in Computer Science

• Publication date

  2008-12-05

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-540-92248-3_22
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• SOFSEM 2007: Theory and Practice of Computer Science

  2007cited by this paper
• Partial vs. Complete Domination: t-Dominating Set

  2007cited by this paper
• Invitation to Fixed-Parameter Algorithms

  2006cited by this paper
• Intuitive Algorithms and t-Vertex Cover

  2006cited by this paper
• Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13-15, 2006, Proceedings

  2006cited by this paper
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems

  2006cited by this paper
• Simplicity is Beauty: Improved Upper Bounds for Vertex Cover

  2005cited by this paper
• Parameterized Complexity of Generalized Vertex Cover Problems

  2005cited by this paper
• Computing small partial coverings

  2003influential reference
• Approximation Algorithms for Combinatorial Optimization

  2003cited by this paper
• Algorithms and Data Structures

  2003cited by this paper
• Improved Approximation Algorithms for the Partial Vertex Cover Problem

  2002cited by this paper
• Using homogenous weights for approximating the partial cover problem

  2001cited by this paper
• Approximation algorithms for partial covering problems

  2001cited by this paper
• Reports in Informatics

  2000cited by this paper
• Massaging a Linear Programming Solution to Give a 2-Approximation for a Generalization of the Vertex Cover Problem

  1998cited by this paper
• The t-Vertex Cover Problem: Extending the Half Integrality Framework with Budget Constraints

  1998cited by this paper
• Color-coding

  1995cited by this paper
• Fixed Parameter Tractability and Completeness III: Some Structural Aspects of the W Hierarchy

  1992cited by this paper
• Ramsey numbers and an approximation algorithm for the vertex cover problem

  1985cited by this paper
• Finding a Maximum Independent Set

  1976cited by this paper
• Approximation algorithms for combinatorial problems

  1973cited by this paper
• FIXED-PARAMETER TRACTABILITY AND COMPLETENESS

  year unknowncited by this paper

• On the Partial Vertex Cover Problem in Bipartite Graphs - a Parameterized Perspective

  2023cites this paper
• Kernelization for Partial Vertex Cover via (Additive) Expansion Lemma

  2022cites this paper
• Covering Many (or Few) Edges with k Vertices in Sparse Graphs

  2022cites this paper
• Partial Vertex Cover on Graphs of Bounded Degeneracy

  2022cites this paper
• On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs

  2021cites this paper
• Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs

  2019cites this paper
• Hitting and Covering Partially

  2018cites this paper
• Parameterized complexity of multiwinner determination: more effort towards fixed-parameter tractability

  2018cites this paper
• Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs

  2017cites this paper
• Calculating approximation guarantees for partial set cover of pairs

  2017cites this paper
• Refined algorithms for hitting many intervals

  2017cites this paper
• The Weighted Partial Vertex Cover Problem in Bipartite Graphs

  2017cites this paper
• Theoretical Computer Science

  2014cites this paper
• Parameterized Algorithms for Graph Partitioning Problems

  2014cites this paper
• On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs

  2014cites this paper
• Association Rules for Recommendations with Multiple Items

  2014cites this paper
• Exact algorithms for problems related to the densest k-set problem

  2014cites this paper
• Approximation et complexité paramétrée de problèmes d'optimisation dans les graphes : partitions et sous-graphes. (Approximation and parameterized complexity for combinatorial optimization problem in graph : partition and subgraph )

  2014cites this paper
• Approximating the Sparsestk-Subgraph in Chordal Graphs

  2013cites this paper
• Partial Interval Set Cover - Trade-Offs between Scalability and Optimality

  2013cites this paper
• Approximation and Online Algorithms

  2013cites this paper
• Fast algorithms for decomposable graphs

  2013cites this paper
• On Partial Vertex Cover on Bipartite Graphs and Trees

  2013cites this paper
• Moderately exponential time and fixed parameter approximation algorithms

  2013cites this paper
• Partial Interval Set Cover { Trade-os

  2013cites this paper
• More on Kernelization

  2013cites this paper
• Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover

  2012cites this paper
• Efficient algorithms for the max \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-vertex cover proble

  2012cites this paper
• Theoretical Computer Science

  2012influential citation
• Parameterized Reductions and Algorithms for Another Vertex Cover Generalization

  2011cites this paper
• Subexponential algorithms for partial cover problems

  2011cites this paper
• Combinatorial Algorithms

  2011cites this paper
• Parameterized algorithm for eternal vertex cover

  2010cites this paper
• The Curse of Connectivity: t-Total Vertex (Edge) Cover

  2010cites this paper
• Computing and Combinatorics, 16th Annual International Conference, COCOON 2010, Nha Trang, Vietnam, July 19-21, 2010. Proceedings

  2010cites this paper
• Pareto Complexity of Two-Parameter FPT Problems: A Case Study for Partial Vertex Cover

  2009cites this paper
• Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms

  2009cites this paper
• Efficient Algorithms for the max k -vertex cover Problem

  year unknowncites this paper