A note on approximating the min–max vertex disjoint paths on directed acyclic graphs

作者：

Highlights：

•

摘要

This paper shows that the FPTAS for the min–max disjoint paths problem on directed acyclic graphs by Yu et al. (2010) [7] can be improved by a rounding and searching technique.

论文关键词：Approximation algorithm,Vertex disjoint paths,Rounding,FPTAS,Directed acyclic graph

论文评审过程：Received 31 May 2010, Revised 13 August 2010, Accepted 20 August 2010, Available online 25 August 2010.

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