PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 13

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  directed graphs
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available Cycles in Bayesian Networks
Shayakhmetova Assem, Litvinenko Natalya, Mamyrbayev Orken, Wójcik Waldemar, Zhamangarin Dusmat
International Journal of Electronics and Telecommunications
|
2021
|
Vol. 67, No. 2
181--186
EN
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.
2
Content available remote Higher-Order Rank Functions on Directed Graphs
Kashiwabara Kenji, Horie Ikumi, Yamaguchi Kazunori
Fundamenta Informaticae
|
2020
|
Vol. 173, nr 1
1--31
EN
We introduce a new higher-order rank function with the capability to completely discriminate non-equivalent nodes. We review the partition lattice and rank functions and situate the existing rank functions and higher-order rank functions within the formalization. We propose a new refining operator and a new rank function that are better than the existing ones in some applications. We also show that the entire topology (graph) can be reconstructed from only our higher-order ranks making it possible to compare nodes in different graphs and to update the equivalence of nodes when an edge is added. Finally, we briefly describe the use of our higher-order rank function in analyzing web pages as a possible application in different domains.
3
Content available remote Companions and an Essential Motion of a Reaction System
Genova Daniela, Hoogeboom Hendrik Jan, Jonoska Nataša
Fundamenta Informaticae
|
2020
|
Vol. 175, nr 1-4
187--199
EN
For a family of sets we consider elements that belong to the same sets within the family as companions. The global dynamics of a reactions system (as introduced by Ehrenfeucht and Rozenberg) can be represented by a directed graph, called a transition graph, which is uniquely determined by a one-out subgraph, called the 0-context graph. We consider the companion classes of the outsets of a transition graph and introduce a directed multigraph, called an essential motion, whose vertices are such companion classes. We show that all one-out graphs obtained from an essential motion represent 0-context graphs of reactions systems with isomorphic transition graphs. All such 0-context graphs are obtained from one another by swapping the outgoing edges of companion vertices.
4
Content available remote Kernels, truth and satisfaction
Schmerl James H.
Bulletin of the Polish Academy of Sciences. Mathematics
|
2019
|
Vol. 67, no. 1
31--35
EN
The Kotlarski-Krajewski-Lachlan Theorem says that every resplendent model of Peano Arithmetic has a full satisfaction class. Enayat and Visser gave a more model-theoretic proof of this theorem. We redo their proof using kernels of directed graphs.
5
Content available remote Preserving λ-scrambling Matrices
Guterman A. E., Maksaev A. M.
Fundamenta Informaticae
|
2018
|
Vol. 162, nr 2/3
119--141
EN
The notion of scrambling index was firstly introduced by Akelbek and Kirkland in 2009. For a primitive digraph D, it is defined as the smallest positive integer k such that for every pair of vertices u and v of D there exist two directed paths of lengths k to a common vertex w. This notion turned out to be useful for several applications, e. g., to estimate eigenvalues of non-negative primitive stochastic matrices. In 2010 Huang and Liu with the background of a memoryless communication system generalized this notion to λ-tuples of vertices and named it λ-th upper scrambling index. These notions can be reformulated in terms of matrix theory. A standard way to generate matrices with the given λ-th upper scrambling index is to apply certain matrix transformations that preserve this index to the existing examples of matrices with known λ-th upper scrambling index. In this paper we completely characterize bijective linear maps preserving λ-th upper scrambling index 1 or 0.
6
Content available Non-factorizable c-valued functions induced by finite connected graphs
Cho I.
Opuscula Mathematica
|
2017
|
Vol. 37, no. 2
225--263
EN
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.
7
Content available Free probability induced by electric resistance networks on energy Hilbert spaces
Cho I., Jorgensen P. E. T.
Opuscula Mathematica
|
2011
|
Vol. 31, no. 4
549-598
EN
We show that a class of countable weighted graphs arising in the study of electric resistance networks (ERNs) are naturally associated with groupoids. Starting with a fixed ERN, it is known that there is a canonical energy form and a derived energy Hilbert space Hε. From Hε, one then studies resistance metrics and boundaries of the ERNs. But in earlier research, there does not appear to be a natural algebra of bounded operators acting on Hε. With the use of our ERN-groupoid, we show that Hε may be derived as a representation Hilbert space of a universal representation of a groupoid algebra [formula], and we display other representations. Among our applications, we identify a free structure of [formula] in terms of the energy form.
8
Content available remote Efficient Implementation of the Italiano Algorithms for Updating the Transitive Closure on Associative Parallel Processors
Nepomniaschay A.
Fundamenta Informaticae
|
2008
|
Vol. 89, nr 2-3
313-329
EN
We propose a simple data structure for an efficient implementation of the Italiano algorithms for the dynamic updating of the transitive closure of a directed graph represented as adjacency matrix on a model of associative (or content addressable) parallel processors with vertical processing (the STAR–machine). Associative versions of the Italiano algorithms are represented as procedures DeleteArc1 and InsertArc1. We prove the correctness of these procedures and evaluate their time and space complexity. We also present the main advantages of associative versions of the Italiano algorithms.
9
Content available remote Graph reduction and its application to DNA sequence assembly
Błażewicz J., Kasprzak M.
Bulletin of the Polish Academy of Sciences. Technical Sciences
|
2008
|
Vol. 56, nr 1
65-70
EN
The results presented here are twofold. First, a heuristic algorithm is proposed which, through removing some unnecessary arcs from a digraph, tends to reduce it into an ad joint and thus simplifies the search for a Hamiltonian cycle. Second, a heuristic algorithm for DNA sequence assembly is proposed, which uses a graph model of the problem instance, and incorporates two independent procedures of reducing the set of arcs - one of them being the former algorithm. Finally, results of tests of the assembly algorithm on parts of chromosome arm 2R of Drosophila melanogaster are presented.
10
Content available remote On the existence of (k,k-1) - kernels in directed graphs
Bród D., Włoch A., Włoch I.
Journal of Mathematics and Applications
|
2006
|
Vol. 28
7-12
EN
We calI a subset J of vertices of a digraph D as a (k, k-1) - kerneI of D, for a fixed k ≥ 2, if all distanees between vertices from J are at Ieast k and the distance from each vertex not belonging to J to the set J is at most k - 1. Some theorems concerning the existence of (k, k - 1) - kernels are proved. The resuIts generalize the well - known Riehardson theorem [9], which says: A digraph without odd circuits has a kernel.
11
Content available remote Exact Computation of Minimum Feedback Vertex Sets with Relational Algebra
Berghammer R., Fronk A.
Fundamenta Informaticae
|
2006
|
Vol. 70, nr 4
301-316
EN
A feedback vertex set of a graph is a subset of vertices containing at least one vertex from every cycle of the graph. Given a directed graph by its adjacency relation, we develop a relational algorithm for computing a feedback vertex set of minimum size. In combination with a BDD-implementation of relations, it allows to exactly solve this NP-hard problem for medium-sized graphs.
12
Zastowanie grafu GP w diagnostyce procesów przemysłowych
Ostasz A., Kościelny J. M.
Pomiary Automatyka Kontrola
|
2005
|
R. 51, nr 9 bis
51--53
PL
Praca zawiera opis formalny grafu GP, a także dyskusje, o jego podstawowych zastosowaniach. Graf GP jest jakościowym modelem diagnozowanego procesu. Wyraża on zależności przyczynowo-skutkowe pomiędzy zmiennymi stanu, sterującymi i pomiarami, uwzględniając także wpływ uszkodzeń na te zmienne. Jako przykład przedstawiono graf GP dla stanowiska laboratoryjnego trzech zbiorników. Podstawowym zastosowaniem grafu jest: wykorzystanie go do projektowania struktury modeli do detekcji uszkodzeń oraz określania relacji uszkodzenia-symptomy.
EN
The paper considers application of causal graph to description of diagnosed process. Presented graph, called Graph of Process (GP), is a qualitative model of the diagnosed process with respect to faults. The graph is used for designing the model structures for fault detection and identifying of fault - symptom relations. Theoretic background of graph GP has been presented as well as an example based on three tank system.
13
Repair servers in unreliable packet-switched computer network with multicast traffic
Grzech A., Zelem J.
Systems Science
|
2002
|
Vol. 28, nr 4
85-108
EN
The paper discusses localization of repair servers at the nodes of an unreliable packet-switched computer communication network, where the latter supports multicast traffic. It is assumed that the multicast traffic is carried in unreliable network, i.e., via unreliable communication channels characterized by failure probabilities. The problem of repair servers localization in a network with unreliable channels and multicast traffic may be considered as a problem of multicast efficiency in terms of network resource consumption and average packets delay introduced by the network. For the purpose of the paper it is assumed that the quality of multicast network in terms of network resource utilization is measured by average delay of transferred packets. The aim of repair servers localization at various nodes of the network considered is to decrease average packet delay delivered by the network.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.