Loading…

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

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.

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2011-11, Vol.77 (6), p.1054-1057
Main Author: Wu, Bang Ye
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2010.08.012