Temat: directed graphs - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: Factoring directed graphs with respect to the cardinal product in polynomial time
Autorzy:: Imrich, Wilfried
Klöckl, Werner
Tematy:: directed graphs
cardinal product
graph algorithms; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743472.pdf Link otwiera się w nowym oknie
Opis:: By a result of McKenzie [4] finite directed graphs that satisfy certain connectivity and thinness conditions have the unique prime factorization property with respect to the cardinal product. We show that this property still holds under weaker connectivity and stronger thinness conditions. Furthermore, for such graphs the factorization can be determined in polynomial time.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 2.

Tytuł:: Factoring directed graphs with respect to the cardinal product in polynomial time II
Autorzy:: Imrich, Wilfried
Klöckl, Werner
Tematy:: directed graphs
cardinal product
graph algorithms; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744038.pdf Link otwiera się w nowym oknie
Opis:: By a result of McKenzie [7] all finite directed graphs that satisfy certain connectivity conditions have unique prime factorizations with respect to the cardinal product. McKenzie does not provide an algorithm, and even up to now no polynomial algorithm that factors all graphs satisfying McKenzie's conditions is known. Only partial results [1,3,5] have been published, all of which depend on certain thinness conditions of the graphs to be factored.
In this paper we weaken the thinness conditions and thus significantly extend the class of graphs for which the prime factorization can be found in polynomial time.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 3.

Tytuł:: On L(2, 1)-Labelings of Oriented Graphs
Autorzy:: Colucci, Lucas
Győri, Ervin
Tematy:: L (2,1)-labeling
directed graphs; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/32361754.pdf Link otwiera się w nowym oknie
Opis:: We extend a result of Griggs and Yeh about the maximum possible value of the L(2, 1)-labeling number of a graph in terms of its maximum degree to oriented graphs. We consider the problem both in the usual definition of the oriented L(2, 1)-labeling number and in some variants we introduce.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 4.

Tytuł:: Cycles in Bayesian Networks
Autorzy:: Shayakhmetova, Assem
Litvinenko, Natalya
Mamyrbayev, Orken
Wójcik, Waldemar
Zhamangarin, Dusmat
Tematy:: Bayesian networks
directed graphs
directed cycles
propagation
Bayesian evidence; Pokaż więcej
Wydawca:: Polska Akademia Nauk. Czytelnia Czasopism PAN
Powiązania:: https://bibliotekanauki.pl/articles/1844619.pdf Link otwiera się w nowym oknie
Opis:: The article is devoted to some critical problems of using Bayesian networks for solving practical problems, in which graph models contain directed cycles. The strict requirement of the acyclicity of the directed graph representing the Bayesian network does not allow to efficiently solve most of the problems that contain directed cycles. The modern theory of Bayesian networks prohibits the use of directed cycles. The requirement of acyclicity of the graph can significantly simplify the general theory of Bayesian networks, significantly simplify the development of algorithms and their implementation in program code for calculations in Bayesian networks.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 5.

Tytuł:: Circuit bases of strongly connected digraphs
Autorzy:: Gleiss, Petra
Leydold, Josef
Stadler, Peter
Tematy:: directed graphs
cycle space
relevant circuits
minimum length basis; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743155.pdf Link otwiera się w nowym oknie
Opis:: The cycle space of a strongly connected graph has a basis consisting of directed circuits. The concept of relevant circuits is introduced as a generalization of the relevant cycles in undirected graphs. A polynomial time algorithm for the computation of a minimum weight directed circuit basis is outlined.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 6.

Tytuł:: Computer verification of 2-Colorabity of linear k-uniform hypergraphs.
Komputerowa weryfikacja dwukolorowalności liniowych k-jednostajnych hipergrafów
Autorzy:: Yevdokymov, Ruslan
Opis:: Hypergraph is called 2-colorable if and only if it is possible to color its vertices such that no hyperedge is monochromatic. In this work we focus on the problem of 2-colorability for a subclass of k-uniform linear hypergraphs. Namely, hypergraphs that satisfy the following property: for every subset of vertices V the size of a set of hyperedges induced by V is at most |V|. There are known counterexamples which show that in the above-mentioned class 2-uniform and 3-uniform hypergraphs are not 2-colorable. But it is still unknown whether such counterexamples exist in the case of k-uniform hypergraphs for k >=4. In this paper we make progress towards resolving this problem using a computational approach. We were able to confirm that the currently only known counterexample for 3-uniform hypergraphs is indeed the smallest. More importantly, we found different bigger counterexamples in the case of 3-uniform hypergraphs which were not previously known. Furthermore, we confirmed that every 4-uniform hypergraph with up to 17 vertices is 2-colorable.
Hipergraf nazywamy dwukolorowalnym wtedy i tylko wtedy, gdy można pokolorować jego wierzchołki tak, by żadna hiperkrawędź nie była monochromatyczna. W tej pracy skupiamy się na problemie dwukolorowania dla pewnej podklasy k-jednostajnych liniowych hipergrafów. Mianowicie, hipergrafów, które spełniają następującą własność: dla każdego podzbioru wierzchołków V rozmiar zbioru hiperkrawędzi indukowanych przez V jest co najwyżej |V|. Znane są kontrprzykłady, które pokazują, że w wyżej wymienionej klasie hipergrafy 2-jednostajne i 3-jednostajne nie są dwukolorowalne. Nie wiadomo jednak, czy takie kontrprzykłady istnieją w przypadku k-jednostajnych hipergrafów dla k >=4. W tej pracy dokonaliśmy postępu w kierunku rozwiązania tego problemu przy użyciu podejścia komputerowego. Udało nam się potwierdzić, że obecnie jedyny znany kontrprzykład dla 3-jednostajnych hipergrafów jest rzeczywiście najmniejszy. Co ważniejsze, znaleźliśmy inne większe kontrprzykłady w przypadku 3-jednostajnych hipergrafów, które nie były wcześniej znane. Ponadto potwierdziliśmy, że każdy 4-jednostajny hipergraf o maksymalnie 17 wierzchołkach jest dwukolorowalny.
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Inne

na półce

Skocz do pozycji: 7.

Tytuł:: Non-factorizable c-valued functions induced by finite connected graphs
Autorzy:: Cho, I.
Tematy:: directed graphs
graph groupoids
Redei zeta functions
graph zeta functions
non-factorizable graphs
gluing on graphs; Pokaż więcej
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Powiązania:: https://bibliotekanauki.pl/articles/255928.pdf Link otwiera się w nowym oknie
Opis:: In this paper, we study factorizability of C-valued formal series at fixed vertices, called the graph zeta functions, induced by the reduced length on the graph groupoids of given finite connected directed graphs. The construction of such functions is motivated by that of Redei zeta functions. In particular, we are interested in (i) “non-factorizability” of such functions, and (ii) certain factorizable functions induced by non-factorizable functions. By constructing factorizable functions from our non-factorizable functions, we study relations between graph zeta functions and well-known number-theoretic objects, the Riemann zeta function and the Euler totient function.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 8.

Tytuł:: The Szymczak functor and shift equivalence on the category of finite sets and finite relations
Autorzy:: Przybylski, Mateusz
Wiseman, Jim
Mrozek, Marian
Opis:: The construction of the Conley index for dynamical systems with discrete time requires an equivalence relation between morphisms induced on index pairs. It follows from the features of the Szymczak functor that shift equivalence, whose equivalence classes are the isomorphism classes in the Szymczak category, is the most general equivalence available. In the case of dynamics modeled from data, the morphisms induced on index pairs are relations. We present an algorithmizable classification of shift equivalence classes for the category of finite sets with arbitrary relations as morphisms. The research is the first step towards the construction of a Conley theory for relations.
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Artykuł

na półce

Skocz do pozycji: 9.

Tytuł:: Wizualizacja grafów w języku Python
Visualization of graphs with Python
Autorzy:: Pażyniowska, Sandra
Opis:: The problem of graph drawing with Python is considered. A range of libraries and packages is collected. Some new algorithms are created and implemented. Data structures for simple geometric graphs are shown.The recursive algorithm for drawing radial trees is created, where the tree center is in the middle of the picture and other nodes are placed on concetric circles. The auxiliary algorithm for finding the tree center and the tree radius is used. For the case of directed acyclic graphs (dags), the modifiedtopological sorting algorithm is created. It is used to draw dags with edges directed from left to right.Gallery of graphs is created with several named graphs, including complete graphs, cubic graphs, quartic graphs, and graphs with square faces. A family of scripts for graph drawing is provided. There is a script for drawing graph nodes on the circle, which is very suitable for Hamiltonian graphs (directed or undirected). All scripts use Gnuplot 4 as a plotting engine, because it is a very fexible program with a command line interface. Main algorithms were tested in order to confirm the complexity.
W pracy zbadano problem rysowania grafów w języku Python. Zebrano szereg bibliotek i pakietów, które współpracują z Pythonem. Stworzono kilka implementacji nowych algorytmów, oraz pokazano struktury danych dla prostych grafów geometrycznych.Zaimplementowano algorytm rekurencyjny do rysowania drzew radialnych, gdzie centrum drzewa jest w środku rysunku, a inne wierzchołki leżą na koncentrycznych kręgach. Stworzono też pomocniczy algorytm do wyznaczania centrum i promienia drzewa. Dla grafów skierowanych acyklicznych (dagów) przedstawiono zmodyfikowany algorytm sortowania topologicznego. Umożliwia on rysowanie dagów z krawędziami skierowanym z lewa na prawo. Stworzono galerię grafów z wieloma grafami nazwanymi, zawierającą grafy pełne, grafy 3-regularne i 4-regularne, oraz grafy ze ścianami kwadratowymi. Zaimplementowano szereg skryptów do rysowania grafów. Jeden ze skryptów rysuje wierzchołki grafu na okręgu, co jest wygodne dla grafówHamiltona, skierowanych i nieskierowanych. Wszystkie skrypty do rysowania używają Gnuplota 4, ze względu na jego elastyczność i interfejs wiersza poleceń. Główne algorytmy przetestowano pod kątem wydajności.
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Inne

na półce

Skocz do pozycji: 10.

Tytuł:: An algorithm for the solution of the traveling salesman problem via disjunctive graphs
Autorzy:: Grabowski, Józef
Tematy:: Directed graphs (digraphs), tournaments
Scheduling theory, deterministic
Special problems of linear programming(transportation, multi-index, etc.); Pokaż więcej
Wydawca:: Polskie Towarzystwo Matematyczne
Powiązania:: https://bibliotekanauki.pl/articles/748529.pdf Link otwiera się w nowym oknie
Opis:: .
From the introduction: "The traveling salesman problem is a problem of combinatorial type. Although problems of this type sometimes have a relatively simple formulation, there are many difficulties associated with their solution even when the most up-to-date computers are used. In the 1970s many papers have been devoted to this problem. The purpose of the vast majority of them has been to find more effective solution algorithms. "In this paper we give the solution of the traveling salesman problem via disjunctive graphs. Up to now the elements of disjunctive graphs have been used to solve problems connected with the determination of an optimal task completion sequence.''
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Informacja

Wyszukujesz frazę "directed graphs" wg kryterium: Temat