Vertex cover problem parameterized above and below tight bounds
From MaRDI portal
Publication:633768
DOI10.1007/S00224-010-9262-YzbMATH Open1209.68276OpenAlexW2152809035MaRDI QIDQ633768FDOQ633768
Authors: G. Gutin, Eun Jung Kim, Michael Lampis, Valia Mitsou 
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
Recommendations
- A probabilistic approach to problems parameterized above or below tight bounds
- Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee
- Improved Parameterized Upper Bounds for Vertex Cover
- Algorithms and Data Structures
- Parameterized complexity of Vertex Cover variants
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- \(E_{11}\) and M theory
- Parameterizing above or below guaranteed values
- Parameterized complexity of Vertex Cover variants
- Scalable parallel algorithms for FPT problems
- Title not available (Why is that?)
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Title not available (Why is that?)
- Fixed-parameter algorithms in analysis of heuristics for extracting networks in linear programs
- Towards fully multivariate algorithmics: some new results and directions in parameter ecology
- Capacitated Domination and Covering: A Parameterized Perspective
- A general method to speed up fixed-parameter-tractable algorithms
- Solving large FPT problems on coarse-grained parallel machines
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- Boxicity of graphs with bounded degree
- Title not available (Why is that?)
- Title not available (Why is that?)
- Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
- Synchronization of a bounded degree graph of cellular automata with nonuniform delays in time \(D\lfloor \log_mD\rfloor\)
- The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
Cited In (27)
- Long directed detours: reduction to 2-disjoint paths
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- Tight gaps for vertex cover in the Sherali-Adams SDP hierarchy
- Combining Two Worlds: Parameterised Approximation for Vertex Cover
- A probabilistic approach to problems parameterized above or below tight bounds
- Graph Layout Problems Parameterized by Vertex Cover
- Matroid-constrained vertex cover
- Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
- A probabilistic approach to problems parameterized above or below tight bounds
- Parameterizing above or below guaranteed values
- Approximating long cycle above Dirac's guarantee
- Note on maximal bisection above tight lower bound
- Title not available (Why is that?)
- A lower bound for the coverability problem in acyclic pushdown VAS
- Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee
- Detours in directed graphs
- Rank vertex cover as a natural problem for algebraic compression
- Domination above \(r\)-independence: does sparseness help?
- Parameterized Reductions and Algorithms for Another Vertex Cover Generalization
- The parameterized complexity of cycle packing: indifference is not an issue
- Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment
- Going far from degeneracy
- Finding detours is fixed-parameter tractable
- Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
- Turán’s Theorem Through Algorithmic Lens
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
This page was built for publication: Vertex cover problem parameterized above and below tight bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q633768)
