Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

Wyszukujesz frazę "bfs" wg kryterium: Temat


Wyświetlanie 1-3 z 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ł
Tytuł:
Modyfikacje algorytmów planowania trasy uwzględniające ograniczenia czasowe i odległościowe
Modification of path-finding algorithms introducing time and distance limitations
Autorzy:
Wolanin, Mateusz
Korniszuk, Klaudia
Smołka, Jakub
Powiązania:
https://bibliotekanauki.pl/articles/98100.pdf
Data publikacji:
2019
Wydawca:
Politechnika Lubelska. Instytut Informatyki
Tematy:
wyznaczanie trasy
rower miejski
algorytm A*
algorytm BFS
route planning
bike sharing system
algorithm A*
algorithm BFS
Opis:
Artykuł przedstawia modyfikacje algorytmów wyszukiwania ścieżki w grafie mające na celu wprowadzenie ograniczeń: czasowych lub odległościowych do znalezionej trasy. Zmodyfikowane zostały dwa algorytmy: A* oraz BFS. Zaproponowana została również modyfikacja algorytmu A*, która łączy atuty tych dwóch algorytmów – wygenerowanie najkrótszych tras o jak najmniejszej liczbie wierzchołków. Zmodyfikowane algorytmy umożliwią stworzenie aplikacji pozwalającej na łatwiejsze i bardziej oszczędne poruszanie się z wykorzystaniem usług typu rowerem miejski.
This paper describes modifications of path-finding algorithms. The modifications add time and distance constraints to generated paths. A* and BFS algorithms are modified. Additionally, A* algorithm modification which combines the advantages (generating the shortest routes with the smallest number of vertices) of A* and BFS is presented.. This allows for creating a route planning app that enables users of bike sharing services to travel more easily and economically.
Źródło:
Journal of Computer Sciences Institute; 2019, 10; 18-23
2544-0764
Pojawia się w:
Journal of Computer Sciences Institute
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On dually compact closed classes of graphs and BFS-constructible graphs
Autorzy:
Polat, Norbert
Powiązania:
https://bibliotekanauki.pl/articles/743184.pdf
Data publikacji:
2003
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
infinite graph
dismantlable graph
constructible graph
BFS-cons-tructible graph
variety
weak-retract
strong product
bridged graph
Helly graph
weakly-modular graph
dually compact closed class
Opis:
A class C of graphs is said to be dually compact closed if, for every infinite G ∈ C, each finite subgraph of G is contained in a finite induced subgraph of G which belongs to C. The class of trees and more generally the one of chordal graphs are dually compact closed. One of the main part of this paper is to settle a question of Hahn, Sands, Sauer and Woodrow by showing that the class of bridged graphs is dually compact closed. To prove this result we use the concept of constructible graph. A (finite or infinite) graph G is constructible if there exists a well-ordering ≤ (called constructing ordering) of its vertices such that, for every vertex x which is not the smallest element, there is a vertex y < x which is adjacent to x and to every neighbor z of x with z < x. Finite graphs are constructible if and only if they are dismantlable. The case is different, however, with infinite graphs. A graph G for which every breadth-first search of G produces a particular constructing ordering of its vertices is called a BFS-constructible graph. We show that the class of BFS-constructible graphs is a variety (i.e., it is closed under weak retracts and strong products), that it is a subclass of the class of weakly modular graphs, and that it contains the class of bridged graphs and that of Helly graphs (bridged graphs being very special instances of BFS-constructible graphs). Finally we show that the class of interval-finite pseudo-median graphs (and thus the one of median graphs) and the class of Helly graphs are dually compact closed, and that moreover every finite subgraph of an interval-finite pseudo-median graph (resp. a Helly graph) G is contained in a finite isometric pseudo-median (resp. Helly) subgraph of G. We also give two sufficient conditions so that a bridged graph has a similar property.
Źródło:
Discussiones Mathematicae Graph Theory; 2003, 23, 2; 365-381
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
    Wyświetlanie 1-3 z 3

    Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies