Autor: Pandu Rangan, C. - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Edge-disjoint paths in permutation graphs
Autorzy:: Gopalakrishnan, C.
Pandu Rangan, C.
Powiązania:: https://bibliotekanauki.pl/articles/971918.pdf
Data publikacji:: 1995
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: algorithm
bridge
connectivity
disjoint paths
permutation graph
Opis:: In this paper we consider the following problem. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two edge-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂, respectively. We give a linear (O(|V|+|E|)) algorithm to solve this problem on a permutation graph.
Źródło:: Discussiones Mathematicae Graph Theory; 1995, 15, 1; 59-72
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: A linear algorithm for the two paths problem on permutation graphs
Autorzy:: Gopalakrishnan, C.
Pandu Rangan, C.
Powiązania:: https://bibliotekanauki.pl/articles/972048.pdf
Data publikacji:: 1995
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: algorithm
bridge
connectivity
disjoint paths
permutation graph
two paths problem
Opis:: 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.
Źródło:: Discussiones Mathematicae Graph Theory; 1995, 15, 2; 147-166
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

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ł

Informacja