Currently displaying 1 – 1 of 1

Showing per page

Order by Relevance | Title | Year of publication

Efficient algorithms for minimal disjoint path problems on chordal graphs

C.P. GopalakrishnanC.R. SatyanC. Pandu Rangan — 1995

Discussiones Mathematicae Graph Theory

Disjoint paths have applications in establishing bottleneck-free communication between processors in a network. The problem of finding minimum delay disjoint paths in a network directly reduces to the problem of finding the minimal disjoint paths in the graph which models the network. Previous results for this problem on chordal graphs were an O(|V| |E|²) algorithm for 2 edge disjoint paths and an O(|V| |E|) algorithm for 2 vertex disjoint paths. In this paper, we give an O(|V| |E|) algorithm for...

Page 1

Download Results (CSV)