Autor: Gopalakrishnan, C. - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: A linear algorithm for the two paths problem on permutation graphs
Autorzy:: Gopalakrishnan, C.
Pandu Rangan, C.
Tematy:: algorithm
bridge
connectivity
disjoint paths
permutation graph
two paths problem; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/972048.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: Edge-disjoint paths in permutation graphs
Autorzy:: Gopalakrishnan, C.
Pandu Rangan, C.
Tematy:: algorithm
bridge
connectivity
disjoint paths
permutation graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/971918.pdf Link otwiera się w nowym oknie
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.
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.
Tematy:: chordal graph
minimal paths
disjoint paths
clique
bfs; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/972049.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja