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

DOI10.1007/S10878-012-9575-7zbMATH Open1315.90056OpenAlexW1983855852MaRDI QIDQ489714FDOQ489714

Authors: Vangelis Th. Paschos, F. 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

Recommendations

• Efficient algorithms for the max \(k\)-vertex cover problem
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• An improved fixed-parameter algorithm for vertex cover
• On approximation of max-vertex-cover
• Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Treewidth Computation and Extremal Combinatorics
• Title not available (Why is that?)
• A measure \& conquer approach for the analysis of exact algorithms
• Computing small partial coverings
• Which problems have strongly exponential complexity?
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Approximation algorithms for maximization problems arising in graph partitioning
• Easy problems for tree-decomposable graphs
• Parameterized Approximation Problems
• Improved Upper Bounds for Partial Vertex Cover
• Improved approximation algorithms for maximum graph partitioning problems
• Improved upper bounds for vertex cover
• Subexponential algorithms for partial cover problems
• Set partitioning via inclusion-exclusion
• Title not available (Why is that?)
• Graph Layout Problems Parameterized by Vertex Cover
• On efficient fixed-parameter algorithms for weighted vertex cover
• Pathwidth of cubic graphs and exact algorithms
• Vertex cover: Further observations and further improvements
• Exact and approximate bandwidth
• Towards fully multivariate algorithmics: some new results and directions in parameter ecology
• Efficient approximation of Min Set Cover by moderately exponential algorithms
• Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
• An exponential time 2-approximation algorithm for bandwidth
• Approximation of min coloring by moderately exponential algorithms
• Exponential-time approximation of weighted set cover
• Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
• Efficient algorithms for the max \(k\)-vertex cover problem
• Algorithms and Data Structures

Cited In (7)

• Efficient algorithms for the max \(k\)-vertex cover problem
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• A note on max \(k\)-vertex cover: faster FPT-AS, smaller approximate kernel and improved approximation
• Parameterized exact and approximation algorithms for maximum \(k\)-set cover and related satisfiability problems
• An exact algorithm for the maximal covering problem
• Super-polynomial approximation branching algorithms
• Voting on multi-issue domains with conditionally lexicographic preferences

Uses Software

• LINDO
• LINGO

This page was built for publication: Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}

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