Finding even subgraphs even faster

作者：

Highlights：

• (Un)directed Eulerian Edge Deletion can be solved in parameterized single exponential time.

• The previous best known algorithm runs in time 2O(klog⁡k)nO(1) [Cygan et al., Algorithmica, 2014].

• Our algorithms are answers to the open problems posed by Cygan et al. [Algorithmica, 2014].

摘要

•(Un)directed Eulerian Edge Deletion can be solved in parameterized single exponential time.•The previous best known algorithm runs in time 2O(klog⁡k)nO(1) [Cygan et al., Algorithmica, 2014].•Our algorithms are answers to the open problems posed by Cygan et al. [Algorithmica, 2014].

论文关键词：Eulerian edge deletion,FPT algorithm,Representative family,Co-graphic matroid,Dynamic programming

论文评审过程：Received 25 July 2017, Revised 12 December 2017, Accepted 12 March 2018, Available online 24 April 2018, Version of Record 13 August 2018.

论文官网地址：https://doi.org/10.1016/j.jcss.2018.03.001