Interval Vertex Deletion Admits a Polynomial Kernel

DOI10.1137/1.9781611975482.103zbMath1432.68185OpenAlexW4242090205MaRDI QIDQ5236287

Meirav Zehavi, Saket Saurabh, Pranabendu Misra, Akanksha Agrawal

Publication date: 15 October 2019

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

Full work available at URL: https://doi.org/10.1137/1.9781611975482.103

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (10)

Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies ⋮ Towards constant-factor approximation for chordal/distance-hereditary vertex deletion ⋮ A polynomial kernel for 3-leaf power deletion ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximate Turing Kernelization for Problems Parameterized by Treewidth ⋮ Unnamed Item ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ A polynomial kernel for bipartite permutation vertex deletion

This page was built for publication: Interval Vertex Deletion Admits a Polynomial Kernel