An Algorithm for Finding Two Edge-Disjoint Paths in Tournaments

Shin-ichi NAKAYAMA  Shigeru MASUYAMA  

Publication
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: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
Keyword: 
edge-disjoint path,  tournament graph,  algorithm,  

Full Text: PDF>>
Buy this Article




Summary: 
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.