Improved Parameterized Upper Bounds for Vertex Cover

DOI10.1007/11821069_21zbMath1132.68421OpenAlexW1559081432MaRDI QIDQ5756684

Ge Xia, Jian'er Chen, Iyad A. Kanj

Publication date: 5 September 2007

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

Full work available at URL: https://doi.org/10.1007/11821069_21

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (33)

Backdoors to Normality for Disjunctive Logic Programs ⋮ Multi-start iterated tabu search for the minimum weight vertex cover problem ⋮ Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes ⋮ Fixed-parameter approximation: conceptual framework and approximability results ⋮ The Impact of Parameterized Complexity to Interdisciplinary Problem Solving ⋮ A top-down approach to search-trees: Improved algorithmics for 3-hitting set ⋮ On the parameterized vertex cover problem for graphs with perfect matching ⋮ Capacitated Domination and Covering: A Parameterized Perspective ⋮ Safe sets and in-dominating sets in digraphs ⋮ Fixed-parameter evolutionary algorithms and the vertex cover problem ⋮ Parameterized proof complexity ⋮ Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover ⋮ The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number ⋮ Solving \#SAT using vertex covers ⋮ Algorithmic meta-theorems for restrictions of treewidth ⋮ Fixed-parameter tractability results for feedback set problems in tournaments ⋮ Iterative compression and exact algorithms ⋮ Parameterized complexity of \textsc{maximum edge colorable subgraph} ⋮ Finding vertex-surjective graph homomorphisms ⋮ Fixed-parameter algorithms for cluster vertex deletion ⋮ Exponential-time approximation of weighted set cover ⋮ Proper Interval Vertex Deletion ⋮ The complexity ecology of parameters: An illustration using bounded max leaf number ⋮ Fixed-Parameter Algorithms for Cluster Vertex Deletion ⋮ On the induced matching problem in Hamiltonian bipartite graphs ⋮ New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition ⋮ On parameterized exponential time complexity ⋮ Parameterized algorithm for eternal vertex cover ⋮ Parameterized learnability of juntas ⋮ Backdoor sets of quantified Boolean formulas ⋮ Parameterized complexity of maximum edge colorable subgraph ⋮ Parameterized Algorithms for Generalized Domination ⋮ Revising Johnson's table for the 21st century

This page was built for publication: Improved Parameterized Upper Bounds for Vertex Cover