Vertex cover problem parameterized above and below tight bounds

DOI10.1007/s00224-010-9262-yzbMath1209.68276OpenAlexW2152809035MaRDI QIDQ633768

Michael Lampis, Valia Mitsou, Eun Jung Kim, Gregory Gutin

Publication date: 30 March 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-010-9262-y

zbMATH Keywords

vertex coverparameterized algorithmsparameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (14)

On Multiway Cut Parameterized above Lower Bounds ⋮ Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter ⋮ Note on maximal bisection above tight lower bound ⋮ Detours in directed graphs ⋮ Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables ⋮ Going Far from Degeneracy ⋮ Unnamed Item ⋮ Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems ⋮ Unnamed Item ⋮ Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization ⋮ Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment ⋮ The parameterized complexity of cycle packing: indifference is not an issue ⋮ Finding Detours is Fixed-Parameter Tractable ⋮ Rank Vertex Cover as a Natural Problem for Algebraic Compression

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Parameterizing above or below guaranteed values
• Boxicity of graphs with bounded degree
• A general method to speed up fixed-parameter-tractable algorithms
• Solving large FPT problems on coarse-grained parallel machines
• Parameterized complexity of Vertex Cover variants
• Synchronization of a bounded degree graph of cellular automata with nonuniform delays in time \(D\lfloor \log_mD\rfloor\)
• Scalable parallel algorithms for FPT problems
• E ₁₁ and M theory
• Capacitated Domination and Covering: A Parameterized Perspective
• Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
• Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
• Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs
• The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number

This page was built for publication: Vertex cover problem parameterized above and below tight bounds