Linear time algorithms for two disjoint paths problems on directed acyclic graphs
type: Item
instance of: scholarly article
title: Linear time algorithms for two disjoint paths problems on directed acyclic graphs
zbMATH Open document ID: 1256.68133
author: Torsten Tholey
published in: Theoretical Computer Science
publication date: 2013-01-07T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 6122474
zbMATH Keywords: graph algorithms
zbMATH Keywords: directed acyclic graphs
zbMATH Keywords: disjoint paths
zbMATH Keywords: 2-disjoint paths problem
MaRDI profile type: Publication
full work available at URL: j.tcs.2012.09.025
OpenAlex ID: W2076850117
cites work: Optimization of LR(k) parsers
cites work: Dominators in Linear Time
cites work: Q4508365
cites work: Output-sensitive reporting of disjoint paths
cites work: Maintaining the classes of 4-edge-connectivity in a graph on-line
cites work: Sparsification—a technique for speeding up dynamic graph algorithms
cites work: The directed subgraph homeomorphism problem
cites work: Fibonacci heaps and their uses in improved network optimization algorithms
cites work: Dominator tree verification and vertex-disjoint paths
cites work: Dominators, Directed Bipolar Orders, and Independent Spanning Trees
cites work: Fast Algorithms for Finding Nearest Common Ancestors
cites work: The disjoint paths problem in quadratic time
cites work: Q3914448
cites work: AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
cites work: Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
cites work: Q4273851
cites work: Rooted routing in the plane
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Q4280137
cites work: Disjoint paths in graphs
cites work: A Polynomial Solution to the Undirected Two Paths Problem
cites work: A quick method for finding shortest pairs of disjoint paths
cites work: Worst-case Analysis of Set Union Algorithms
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Solving the 2-disjoint paths problem in nearly linear time
cites work: Improved Algorithms for the 2-Vertex Disjoint Paths Problem
cites work: 2-linked graphs
cites work: The 2-linkage problem for acyclic digraphs
DOI: 10.1016/J.TCS.2012.09.025
description: scientific article; zbMATH DE number 6122474