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

作者：Wu Bang Ye^*

来源：Journal of Computer and System Sciences, 2011, 77(6): 1054-1057.

DOI：10.1016/j.jcss.2010.08.012

• Approximation algorithm
• Vertex disjoint paths
• Rounding
• FPTAS
• Directed acyclic graph

This paper shows that the FFTAS 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.

• 出版日期2011-11