Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1414043, author = {Eiben, Eduard and Ordyniak, Sebastian and Ramanujan, M.S. and Bergougnoux, Benjamin and Ganian, Robert}, address = {Nemecko}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science, {MFCS} 2017, August 21-25, 2017 - Aalborg, Denmark}, doi = {http://dx.doi.org/10.4230/LIPIcs.MFCS.2017.36}, edition = {83}, editor = {Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin}, keywords = {parameterized algorithms; kernelization; (directed) feedback vertex set}, howpublished = {elektronická verze "online"}, language = {eng}, location = {Nemecko}, isbn = {978-3-95977-046-0}, pages = {1-15}, publisher = {LIPIcs}, title = {Towards a Polynomial Kernel for Directed Feedback Vertex Set}, url = {http://drops.dagstuhl.de/opus/volltexte/2017/8112/}, year = {2017} }
TY - JOUR ID - 1414043 AU - Eiben, Eduard - Ordyniak, Sebastian - Ramanujan, M.S. - Bergougnoux, Benjamin - Ganian, Robert PY - 2017 TI - Towards a Polynomial Kernel for Directed Feedback Vertex Set PB - LIPIcs CY - Nemecko SN - 9783959770460 KW - parameterized algorithms KW - kernelization KW - (directed) feedback vertex set UR - http://drops.dagstuhl.de/opus/volltexte/2017/8112/ L2 - http://drops.dagstuhl.de/opus/volltexte/2017/8112/ N2 - In the Directed Feedback Vertex Set (DFVS) problem, the input is a directed graph D and an integer k. The objective is to determine whether there exists a set of at most k vertices intersecting every directed cycle of D. DFVS was shown to be fixed-parameter tractable when parameterized by solution size by Chen, Liu, Lu, O'Sullivan and Razgon [JACM 2008]; since then, the existence of a polynomial kernel for this problem has become one of the largest open problems in the area of parameterized algorithmics. In this paper, we study DFVS parameterized by the feedback vertex set number of the underlying undirected graph. We provide two main contributions: a polynomial kernel for this problem on general instances, and a linear kernel for the case where the input digraph is embeddable on a surface of bounded genus. ER -
EIBEN, Eduard, Sebastian ORDYNIAK, M.S. RAMANUJAN, Benjamin BERGOUGNOUX a Robert GANIAN. Towards a Polynomial Kernel for Directed Feedback Vertex Set. Online. In Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin. \textit{42nd International Symposium on Mathematical Foundations of Computer Science, $\{$MFCS$\}$ 2017, August 21-25, 2017 - Aalborg, Denmark}. 83. vyd. Nemecko: LIPIcs, 2017, s.~1-15. ISBN~978-3-95977-046-0. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.MFCS.2017.36.
|