Faster exact algorithms for some terminal set problems

作者：

Highlights：

• A general methodology to obtain faster exact exponential time algorithms well-studied terminal set problems is presented.

• It combines polynomial time, fixed parameter tractable and exact exponential time algorithms for the non-terminal versions.

• We break the O⁎(2n) barrier for the classic Node Multiway Cut and Directed Subset Feedback Vertex Set problems.

摘要

•A general methodology to obtain faster exact exponential time algorithms well-studied terminal set problems is presented.•It combines polynomial time, fixed parameter tractable and exact exponential time algorithms for the non-terminal versions.•We break the O⁎(2n) barrier for the classic Node Multiway Cut and Directed Subset Feedback Vertex Set problems.

论文关键词：Exact exponential time algorithms,Terminal set problems,Multiway cut,Feedback vertex set

论文评审过程：Received 17 August 2015, Revised 29 September 2016, Accepted 12 April 2017, Available online 4 May 2017, Version of Record 11 June 2017.

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