Vertex cover problem parameterized above and below tight bounds
From MaRDI portal
Publication:633768
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
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 11 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
