- Tytuł:
- Efficient algorithms for minimal disjoint path problems on chordal graphs
- Autorzy:
-
Gopalakrishnan, C.
Satyan, C.
Pandu Rangan, C. - Powiązania:
- https://bibliotekanauki.pl/articles/972049.pdf
- Data publikacji:
- 1995
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
chordal graph
minimal paths
disjoint paths
clique
bfs - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 1995, 15, 2; 119-145
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł