Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

A linear algorithm for the two paths problem on permutation graphs

C.P. GopalakrishnanC. Pandu Rangan — 1995

Discussiones Mathematicae Graph Theory

The 'two paths problem' is stated as follows. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two vertex-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂ respectively. In this paper we give a linear (O(|V|+ |E|)) algorithm to solve the above problem on a permutation graph.

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)