A note on approximating the min-max vertex disjoint paths on directed acyclic graphs
type: Item
instance of: scholarly article
title: A note on approximating the min-max vertex disjoint paths on directed acyclic graphs
zbMATH Open document ID: 1233.68149
author: Bang Ye Wu
published in: Journal of Computer and System Sciences
publication date: 2012-01-11T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 5996366
zbMATH Keywords: approximation algorithm
zbMATH Keywords: vertex disjoint path
zbMATH Keywords: rounding
zbMATH Keywords: FPTAS
zbMATH Keywords: directed acyclic graph
MaRDI profile type: Publication
full work available at URL: j.jcss.2010.08.012
OpenAlex ID: W1997781700
cites work: An improved FPTAS for Restricted Shortest Path.
cites work: Efficient Algorithms for k-Disjoint Paths Problems on DAGs
cites work: Approximation Schemes for the Restricted Shortest Path Problem
cites work: Length-bounded disjoint paths in planar graphs
cites work: The complexity of finding two disjoint paths with min-max objective function
cites work: A simple efficient approximation scheme for the restricted shortest path problem
cites work: Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax \(k\) vertex-disjoint paths in a directed acyclic graph
DOI: 10.1016/J.JCSS.2010.08.012
description: scientific article; zbMATH DE number 5996366