Technical Report 394-1994

Title

The General Two-Path Problem in time O(m log n), extended abstract

Author

Jens Gustedt

Source

Download as [ps.gz]

Classification

not available

Keywords

not available

Abstract

The General Two Path Problem is the problem of finding vertex disjoint paths between two pairs of terminals in an arbitrary graph G. We show that this problem is solvable in time O(m log n), where n and m are the numbers of vertices and edges of G resp.