Temat: disjoint paths - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: A proof of mengers theorem by contraction
Autorzy:: Göring, Frank
Tematy:: connectivity
disjoint paths
digraph
Menger; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743549.pdf Link otwiera się w nowym oknie
Opis:: A short proof of the classical theorem of Menger concerning the number of disjoint AB-paths of a finite graph for two subsets A and B of its vertex set is given. The main idea of the proof is to contract an edge of the graph.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 2.

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ł

na półce

Skocz do pozycji: 3.

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ł

na półce

Skocz do pozycji: 4.

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ł

na półce

Skocz do pozycji: 5.

Tytuł:: The Turán number of three disjoint paths
Autorzy:: Deng, Jinghua
Hou, Jianfeng
Zeng, Qinghou
Tematy:: Turán number
disjoint paths
extremal graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/59945792.pdf Link otwiera się w nowym oknie
Opis:: The Turán number of a graph $H$, ex$(n,H)$, is the maximum number of edges in an $n$-vertex graph that does not contain $H$ as a subgraph. Let $P_k$ denote the path on $k$ vertices and let $ \bigcup_{i=1}^{m}P_{k_{i}} $ denote the disjoint union of $P_{k_i}$ for $1\le i\le m$; in particular, write $ \bigcup_{i=1}^{m}P_{k_{i}}=mP_k $ if $k_i=k$ for all $1\le i\le m$. Yuan and Zhang determined $ \text{ex}(n,\bigcup_{i=1}^{m}P_{k_{i}}) $ for all integers $n$ if at most one of $k_{1},...,k_{m}$ is odd. Much less is known for all integers $n$ if at least two of $k_{1},...,k_{m}$ are odd. Partial results such as $\text{ex}(n,mP_3)$, $\text{ex}(n,P_{3}\cup P_{2ℓ+1})$, $(n,2P_{5})$, $\text{ex}(n,2P_{7})$ and $\text{ex}(n,3P_{5})$ have been established by several researchers. In this paper, we develop new functions and determine ex$(n,3P_{7})$ and $ \text{ex}(n,2P_{3}\cup P_{2ℓ+1})$ for all integers $n$. We also characterize all the extremal graphs. Both results contribute to a conjecture of Yuan and Zhang.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 6.

Tytuł:: A formal approach to Mengers theorem
Autorzy:: Bonacina, Roberta
Misselbeck-Wessel, Daniel
Tematy:: disjoint paths
separating set
inductive definition
entailment; Pokaż więcej
Wydawca:: Uniwersytet Jagielloński. Wydawnictwo Uniwersytetu Jagiellońskiego
Powiązania:: https://bibliotekanauki.pl/articles/61521258.pdf Link otwiera się w nowym oknie
Opis:: Menger’s graph theorem equates the minimum size of a separating set for non-adjacent vertices a and b with the maximum number of disjoint paths between a and b. By capturing separating sets as models of an entailment relation, we take a formal approach to Menger’s result. Upon showing that inconsistency is characterised by the existence of sufficiently many disjoint paths, we recover Menger’s theorem by way of completeness.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 7.

Tytuł:: An Algorithm for Enumerating SRLG Diverse Path Pairs
Autorzy:: Gomes, T.
Craveirinha, J.
Tematy:: routing
SRLG disjoint shortest paths
telecommunication networks; Pokaż więcej
Wydawca:: Instytut Łączności - Państwowy Instytut Badawczy
Powiązania:: https://bibliotekanauki.pl/articles/308463.pdf Link otwiera się w nowym oknie
Opis:: Telecommunication networks are intrinsically multi-layered, a single failure at a lower level usually corresponds to a multi-failure scenario at an upper layer. In this context, the concept of shared risk link group (SRLG) allows an upper layer to select, for a given active path (AP), a backup path (BP), which avoids every SRLG that may involve the selected AP, in the event of a failure. That is a SRLG diverse path set maybe defined as a set of paths, between an origin and a destination, such that no pair of paths can be simultaneously affected by any given failure (or risk) in a single failure scenario. Firstly we present the formulation of the SRLG di- verse path pair calculation problem in a directed network. An algorithm for enumerating SRLG diverse paths, by non decreasing cost of their total (additive) cost will be presented, which is based on an algorithm proposed for generating minimal cost node disjoint path pairs. The SRLG diverse path pairs may be node or arc disjoint, with or without length constraints. Computational results will be presented to show the efficiency of the proposed algorithm for obtaining node or arc disjoint SRLG diverse path pairs in undirected networks.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 8.

Tytuł:: Arc-Disjoint Hamiltonian Paths in Strong Round Decomposable Local Tournaments
Autorzy:: Meng, Wei
Tematy:: local tournament
round-decomposable
arc-disjoint Hamiltonian paths; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/32083838.pdf Link otwiera się w nowym oknie
Opis:: Thomassen, [Edge-disjoint Hamiltonian paths and cycles in tournaments, J. Combin. Theory Ser. B 28 (1980) 142–163] proved that every strong tournament has a pair of arc-disjoint Hamiltonian paths with distinct initial vertices and distinct terminal vertices if and only if it is not an almost transitive tournament of odd order. As a subclass of local tournaments, Li et al. [Arc-disjoint Hamiltonian cycles in round decomposable local tournaments, Discuss. Math. Graph Theory 38 (2018) 477–490] confirmed the existence of such two paths in 2-strong round decomposable local tournaments. In this paper, we show that every strong, but not 2-strong, round decomposable local tournament contains a pair of arc-disjoint Hamiltonian paths with distinct initial vertices and distinct terminal vertices except for three classes of digraphs. Thus Thomassen's result is partly extended to round decomposable local tournaments. In addition, we also characterize strong round digraphs which contain a pair of arc-disjoint Hamiltonian paths with distinct initial vertices and distinct terminal vertices.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 9.

Tytuł:: Zastosowanie metod wyznaczania przepływu w sieciach do planowania manewru wojsk
Application of methods for determining flows in networks to military forces manoeuvre planning
Autorzy:: Tarapata, Z.
Tematy:: planowanie manewru
drogi rozłączne
przepływy w sieciach
manoeuvre planning
disjoint paths
flows in networks; Pokaż więcej
Wydawca:: Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego
Powiązania:: https://bibliotekanauki.pl/articles/305957.pdf Link otwiera się w nowym oknie
Opis:: W artykule przedstawiono opis sposobu wykorzystania metod wyznaczania przepływu w sieciach do rozwiązania specyficznego problemu planowania manewru wojsk. Zdefiniowano model sieci formalnej, bazującej na danych z cyfrowej mapy terenu, wykorzystywanej jako model środowiska w problemie planowania manewru. Sformułowano optymalizacyjny problem planowania przegrupowania K obiektów z rejonu startowego (reprezentowanego przez podzbiór wierzchołków sieci formalnej) do rejonu docelowego, z dodatkowym ograniczeniem na rozłączność dróg. Opisano sposób modyfikacji sieci pierwotnej oraz poszukiwania jednego z rozwiązań dopuszczalnych sformułowanego problemu planowania przegrupowania z użyciem metody znajdowania przepływu maksymalnego w sieci zmodyfikowanej. Przedyskutowano metodę poszukiwania rozwiązania optymalnego bazującą na algorytmie znajdowania przepływu zaspokajającego o minimalnym koszcie w pewnej sieci zastępczej. Opisane metody zilustrowano przykładami obliczeniowymi. Oszacowano złożoność obliczeniową prezentowanych algorytmów. Artykuł kończy omówienie rozszerzeń sformułowanego problemu wyjściowego oraz metod ich rozwiązywania.
In the paper an application of methods for determining flows in networks to military forces maneuver planning is presented. Model of formal network as environment model for manoeuvre planning based on digital maps is defined. Optimization problem of redeployment planning of K objects from source region to destination one taking into account paths disjointness is considered. The method for finding one of the acceptable solution of considered redeployment problem based on method of solving maximum flow problem is described. The method for finding optimal solution of considered problem based on method of solving minimum cost network flow problem in some substitute network is defined. For both of the methods computational complexity is estimated. Some computational examples of presented methods are shown.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 10.

Tytuł:: Metody rozwiązywania problemu najkrótszych dróg wierzchołkowo rozłącznych przechodzących przez wybrane wierzchołki w sieciach o strukturze kraty
Methods for solving node-disjoint shortest paths visiting specified nodes problem in mesh networks
Autorzy:: Tarapata, Z.
Wrocławski, S.
Tematy:: drogi rozłączne wierzchołkowo
symulacja pola walki
generowanie podgrafów
planowanie przemieszczania
node-disjoint paths
battlefield simulation
subgraphs generating
movement planning; Pokaż więcej
Wydawca:: Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego
Powiązania:: https://bibliotekanauki.pl/articles/210591.pdf Link otwiera się w nowym oknie
Opis:: W pracy zaprezentowano modele i metody służące do rozwiązywania problemu wyznaczania K dróg wierzchołkowo rozłącznych przechodzących przez wybrane wierzchołki, o najmniejszym sumarycznym koszcie w sieci prostokątnej (tzw. kracie) opartej o graf G. Zdefiniowano problem jako zadanie optymalizacji liniowej ciągłej oraz przedstawiono dwie metody przybliżone jego rozwiązania: metodę SGDP (bazującą na pewnej iteracyjnej procedurze wyznaczania dróg najkrótszych w podgrafach grafu G) oraz modyfikację metody Edmondsa-Karpa rozwiązywania problemu wyznaczania przepływu zaspokajającego o minimalnym koszcie. Przeprowadzono analizę ich złożoności oraz dokonano porównania jakości obu metod na podstawie eksperymentalnych wyników.
In the paper, models and methods for solving K node-disjoint shortest paths visiting specified nodes problem in mesh networks (based on a graph G) have been presented. The problem has been defined as continuous linear programming problem and two approximation methods for solving it have been presented: SGDP method (based on some iterative procedure of finding shortest paths in subgraphs of G) and modification of Edmond's-Karp method for solving minimal cost flow problem. Complexity and quality analysis of presented methods based on experimental results using real terrain models have been done.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Informacja

Wyszukujesz frazę "disjoint paths" wg kryterium: Temat