Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee

DOI10.1137/1.9781611974331.ch80zbMath1398.68234arXiv1509.03990OpenAlexW2952307946MaRDI QIDQ4575661

Shivam Garg, Geevarghese Philip

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1509.03990

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (16)

Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems ⋮ Parameterizing edge modification problems above lower bounds ⋮ A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter ⋮ Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments ⋮ Elimination Distances, Blocking Sets, and Kernels for Vertex Cover ⋮ Detours in directed graphs ⋮ Going Far from Degeneracy ⋮ The Complexity of Finding (Approximate Sized) Distance-d Dominating Set in Tournaments ⋮ Exploiting c-Closure in Kernelization Algorithms for Graph Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Balanced stable marriage: how close is close enough? ⋮ New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition ⋮ Rank Vertex Cover as a Natural Problem for Algebraic Compression ⋮ Smaller Parameters for Vertex Cover Kernelization ⋮ Above guarantee parameterization for vertex cover on graphs with maximum degree 4

This page was built for publication: Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee