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
type: Item
instance of: scholarly article
title: 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
zbMATH Open document ID: 1213.05059
author: Chih-Chiang Yu
author: Chien-Hsin Lin
author: Biing-Feng Wang
published in: Journal of Computer and System Sciences
publication date: 2010-10-07T00:00:00Z
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W05
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 90C39
zbMATH DE Number: 5796725
zbMATH Keywords: algorithms
zbMATH Keywords: directed acyclic graphs
zbMATH Keywords: dynamic programming
zbMATH Keywords: fully polynomial-time approximation schemes
zbMATH Keywords: planar graphs
zbMATH Keywords: pseudo-polynomial time
zbMATH Keywords: vertex-disjoint paths
MaRDI profile type: Publication
full work available at URL: j.jcss.2010.01.013
OpenAlex ID: W2093083747
cites work: Introduction to algorithms
cites work: Efficient Algorithms for k-Disjoint Paths Problems on DAGs
cites work: The directed subgraph homeomorphism problem
cites work: An efficient algorithm for \(k\)-pairwise disjoint paths in star graphs
cites work: An efficient algorithm for the \(k\)-pairwise disjoint paths problem in hypercubes
cites work: Approximation Schemes for the Restricted Shortest Path Problem
cites work: The complexity of finding maximum disjoint paths with length constraints
cites work: On the Computational Complexity of Combinatorial Problems
cites work: General vertex disjoint paths in series-parallel graphs
cites work: The maximum edge-disjoint paths problem in complete graphs
cites work: The complexity of finding two disjoint paths with min-max objective function
cites work: Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Solving the 2-disjoint paths problem in nearly linear time
cites work: Length-bounded disjoint paths in planar graphs
cites work: A linear-time algorithm for edge-disjoint paths in planar graphs
DOI: 10.1016/J.JCSS.2010.01.013
description: scientific article; zbMATH DE number 5796725