Rank Vertex Cover as a Natural Problem for Algebraic Compression
From MaRDI portal
Publication:5232153
DOI10.1137/17M1154370zbMath1419.05203arXiv1705.02822OpenAlexW2963443205MaRDI QIDQ5232153
Fahad Panolan, Saket Saurabh, Meirav Zehavi, Syed M. Meesum
Publication date: 29 August 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1705.02822
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An improved fixed-parameter algorithm for vertex cover
- Fundamentals of parameterized complexity
- Vertex cover problem parameterized above and below tight bounds
- The complexity of König subgraph problems and above-guarantee vertex cover
- Improved upper bounds for vertex cover
- Refined memorization for vertex cover
- Almost 2-SAT is fixed-parameter tractable
- Which problems have strongly exponential complexity?
- PRIMES is in P
- A kernel of order \(2k-c\log k\) for vertex cover
- Vertex Cover: Further Observations and Further Improvements
- On Multiway Cut Parameterized above Lower Bounds
- Extremal Combinatorics
- Paths, Flowers and Vertex Cover
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Nondeterminism within $P^ * $
- Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee
- A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
- Faster Parameterized Algorithms Using Linear Programming
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
- Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination
This page was built for publication: Rank Vertex Cover as a Natural Problem for Algebraic Compression
