Approximation and Kernelization for Chordal Vertex Deletion

DOI10.1137/1.9781611974782.91zbMATH Open1410.68300arXiv1605.03001OpenAlexW2374265145MaRDI QIDQ4575834

Author name not available (Why is that?)

Publication date: 16 July 2018

Published in: (Search for Journal in Brave)

Abstract: The Chordal Vertex Deletion (ChVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel for ChVD under the parameterization by the solution size, as well as poly(opt) approximation algorithm. The first result answers an open problem of Marx from 2006 [WG 2006, LNCS 4271, 37-48].

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

Mathematics Subject Classification ID

No records found.

This page was built for publication: Approximation and Kernelization for Chordal Vertex Deletion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575834)