An Algorithm for Finding Two Edge-Disjoint Paths in Tournaments

Shin-ichi NAKAYAMA  Shigeru MASUYAMA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E83-A   No.12   pp.2672-2678
Publication Date: 2000/12/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
edge-disjoint path,  tournament graph,  algorithm,  

Full Text: PDF(370.2KB)>>
Buy this Article

This paper presents an O(n2)-time algorithm for constructing two edge-disjoint paths connecting two given pairs of vertices in a given tournament graph. It improves the time complexity of a previously known O(n4)-time algorithm.