Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: minimal paths

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Efficient algorithms for minimal disjoint path problems on chordal graphs

100%

Gopalakrishnan C., Satyan C., Pandu Rangan C.

Discussiones Mathematicae Graph Theory

1995

tom 15

nr 2

119-145

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 2 vertex disjoint paths and an O(|V|+|E|) algorithm for 2 edge disjoint paths, which is a significant improvement over the previous result.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Gopalakrishnan C.

1 Pandu Rangan C.

1 Satyan C.

1 1995

Wyniki wyszukiwania

Efficient algorithms for minimal disjoint path problems on chordal graphs