Edge-disjoint paths in permutation graphs

Szczegóły
Opis

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
Źródło:: Discussiones Mathematicae Graph Theory; 1995, 15, 1; 59-72
2083-5892
Język:: angielski
Prawa:: Wszystkie prawa zastrzeżone. Swoboda użytkownika ograniczona do ustawowego zakresu dozwolonego użytku
Dostawca treści:: Biblioteka Nauki
: Artykuł

Przejdź do źródła

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.

Informacja

Powiązane pozycje