Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}

DOI10.1007/s10878-012-9575-7zbMath1315.90056OpenAlexW1983855852MaRDI QIDQ489714

Vangelis Th. Paschos, Frederico Della Croce

Publication date: 21 January 2015

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-012-9575-7

zbMATH Keywords

measure-and-conquerexact exponential algorithmsmaximum \(k\)-vertex problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items

FPT approximation schemes for maximizing submodular functions ⋮ Super-polynomial approximation branching algorithms ⋮ Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems ⋮ Voting on multi-issue domains with conditionally lexicographic preferences

Uses Software

• LINDO
• LINGO

Cites Work

• Unnamed Item
• Unnamed Item
• Exact and approximate bandwidth
• Improved upper bounds for vertex cover
• Improved approximation algorithms for maximum graph partitioning problems
• Approximation of min coloring by moderately exponential algorithms
• Exponential-time approximation of weighted set cover
• Computing small partial coverings
• Efficient approximation of Min Set Cover by moderately exponential algorithms
• Pathwidth of cubic graphs and exact algorithms
• Which problems have strongly exponential complexity?
• Subexponential algorithms for partial cover problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
• Vertex Cover: Further Observations and Further Improvements
• Efficient Algorithms for the max k -vertex cover Problem
• Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
• Easy problems for tree-decomposable graphs
• A measure & conquer approach for the analysis of exact algorithms
• Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
• Parameterized Approximation Problems
• Treewidth Computation and Extremal Combinatorics
• Set Partitioning via Inclusion-Exclusion
• Graph Layout Problems Parameterized by Vertex Cover
• Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
• An Exponential Time 2-Approximation Algorithm for Bandwidth
• On efficient fixed-parameter algorithms for weighted vertex cover
• Improved Upper Bounds for Partial Vertex Cover
• Algorithms and Data Structures