- 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ł