Improved upper bounds for vertex cover

DOI10.1016/j.tcs.2010.06.026zbMath1205.05217MaRDI QIDQ708228

Publication date: 11 October 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.06.026

zbMATH Keywords

vertex cover; NP-complete problem; parameterized algorithm; branch-and-search

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Maximum Minimal Vertex Cover Parameterized by Vertex Cover, Unnamed Item, Unnamed Item, Parameterized Algorithms for Queue Layouts, Parameterized Algorithms for Book Embedding Problems, Why Is Maximum Clique Often Easy in Practice?, Rank Vertex Cover as a Natural Problem for Algebraic Compression, 3-Hitting set on bounded degree hypergraphs: Upper and lower bounds on the kernel size, Slightly Superexponential Parameterized Problems, Conflict free version of covering problems on graphs: classical and parameterized, Your rugby mates don't need to know your colleagues: triadic closure with edge colors, Parameterized Pre-Coloring Extension and List Coloring Problems, On the ordered list subgraph embedding problems, Tractability in constraint satisfaction problems: a survey, Treewidth and pathwidth parameterized by the vertex cover number, Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter, Beyond bidimensionality: parameterized subexponential algorithms on directed graphs, A novel parameterised approximation algorithm for \textsc{minimum vertex cover}, Parameterized complexity of vertex deletion into perfect graph classes, Solving min ones 2-SAT as fast as vertex cover, A note on the parameterized complexity of unordered maximum tree orientation, Local search: is brute-force avoidable?, Guarantees and limits of preprocessing in constraint satisfaction and reasoning, Confronting intractability via parameters, On the parameterized complexity of vertex cover and edge cover with connectivity constraints, Complexity of conflict-free colorings of graphs, Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}, On the parameterized complexity of computing balanced partitions in graphs, An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem, On optimal approximability results for computing the strong metric dimension, On computing the minimum 3-path vertex cover and dissociation number of graphs, Implicit branching and parameterized partial cover problems, On families of categorial grammars of bounded value, their learnability and related complexity questions, Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover, Dynamic parameterized problems, A parameterized complexity view on collapsing \(k\)-cores, Compactors for parameterized counting problems, An exact algorithm for maximum independent set in degree-5 graphs, Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover, A \(2k\)-kernelization algorithm for vertex cover based on crown decomposition, Approximation for vertex cover in \(\beta\)-conflict graphs, A refined algorithm for maximum independent set in degree-4 graphs, Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem, Parameterized approximation via fidelity preserving transformations, The many facets of upper domination, Backdoors for linear temporal logic, Multivariate algorithmics for finding cohesive subnetworks, Algorithms parameterized by vertex cover and modular width, through potential maximal cliques, On the complexity of wafer-to-wafer integration, Extended formulations for vertex cover, Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}, Proper interval vertex deletion, Parameterized complexity of \textsc{maximum edge colorable subgraph}, Maximum independent sets near the upper bound, An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses, Domination chain: characterisation, classical complexity, parameterised complexity and approximability, Parameterized algorithms for book embedding problems, Efficient parallel algorithms for parameterized problems, Polynomial kernels for vertex cover parameterized by small degree modulators, Backdoors to tractable answer set programming, Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization, Obtaining matrices with the consecutive ones property by row deletions, New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set, Faster exact algorithms for some terminal set problems, A multivariate framework for weighted FPT algorithms, The graph motif problem parameterized by the structure of the input graph, On the complexity of various parameterizations of common induced subgraph isomorphism, Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion}, Maximum common induced subgraph parameterized by vertex cover, Parameterized and exact algorithms for class domination coloring, On the Complexity Landscape of the Domination Chain, A Parameterized Algorithm for Bounded-Degree Vertex Deletion, The Monotone Circuit Value Problem with Bounded Genus Is in NC, Strong Backdoors for Default Logic, Algorithmic Aspects of Upper Domination: A Parameterised Perspective, Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics, A Basic Parameterized Complexity Primer, Backdoors to Satisfaction, What’s Next? Future Directions in Parameterized Complexity, Maximum Minimal Vertex Cover Parameterized by Vertex Cover, On the Parameterized Parallel Complexity and the Vertex Cover Problem, Parameterized and Exact Algorithms for Class Domination Coloring, Parameterized Complexity of Vertex Deletion into Perfect Graph Classes, A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter, Parameterized Power Vertex Cover, A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion, Lower Bounds for the Graph Homomorphism Problem, A Multivariate Approach for Weighted FPT Algorithms

Uses Software

DIMACS

Cites Work