China 
Africa 
Explore chapters and articles related to this topic
Graph Algorithms I
Published in R. Balakrishnan, Sriraman Sridharan, Discrete Mathematics, 2019
R. Balakrishnan, Sriraman Sridharan
After seeing how the graphs are represented inside a computer, two minimum spanning tree algorithms in a connected simple graph with weights associated to each edge, one due to Prim and the other invented by Kruskal are presented. Then, shortest path problems in a weighted directed graph are studied. First, the single-source shortest path problem due to Dijkstra is presented. As an application, an algorithm is given to test the bipartiteness of a graph. Next, a single-source shortest path algorithm for negative edge weights is given. Then, all-pairs shortest path problem due to Floyd and the transitive closure algorithm by Warshall are given. Floyd’s algorithm is applied to find eccentricities of vertices, radius and diameter of a graph.
Foundation and Application of Expert System Verification and Validation
Published in Jay Liebowitz, The Handbook of Applied Expert Systems, 2019
G is formed by (N,E) where N is a set of nodes and E is a set of directed edges. Each fact, rule, module, or metarule of KBmax is represented by a different node in N. Each node is labeled by the object it represents. There is an edge from ni, to nj when the object labeling ni depends on the object labeling nj by three possible dependencies. The transitive closure is computed (C of G is a directed graph such that there is an edge v,w in C if there is a directed path from ν to w in G). Those nodes that cannot be reached from the nodes corresponding to the modified objects, represent the objects forming the set KBinv,
Special Digraph Models
Published in Jonathan L. Gross, Jay Yellen, Mark Anderson, Graph Theory and Its Applications, 2018
Jonathan L. Gross, Jay Yellen, Mark Anderson
definition: The transitive closure R* of a binary relation R is the relation R* defined by (x, y) ∈ R* if and only if there exists a sequence x = v0, v1, v2…, vk = y such that k ≥ 1 and (vi, vi+1) ∈ R, for i = 0, 1,⋯, k − 1.
A hybrid meta-heuristic approach for optimization of routing and spectrum assignment in Elastic Optical Network (EON)
Published in Enterprise Information Systems, 2021
Warshall’s algorithm is used to identify a graph’s transitive closure. This algorithm fails to detect all possible shortest paths more accurately. Floyd’s algorithm is available to find the shortest route environment, but this is not appropriate for the wireless sensor network (WSN). If weights are designated to the paths in Warshall’s algorithm and shortest paths are discovered with all sets of nodes, which are termed as Floyd’s algorithm mentioned in algorithm 1 (Khan, Konar, and Chakraborty 2014). Floyd–Warshall’s algorithm fails when the negative cycles are present in the network. In other hand, Bellman–Ford algorithm is very similar to Dijkstra’s algorithm but it can handle negative cycles. So, the advantages of both Floyd Warshall and Bellman algorithms are combined in our new improved algorithm.
Fifty years of similarity relations: a survey of foundations and applications
Published in International Journal of General Systems, 2022
It is instructive to see first what happens in the crisp case: If R is a reflexive and symmetric crisp relation on a finite set X, it can be represented by a graph with vertices the elements of X and with two vertices x and y connected by an edge when xRy. Its transitive closure is the smallest graph that contains and such that all its connected components are complete subgraphs. This makes an equivalence relation. Figure 1 shows a graph corresponding to a reflexive and symmetric relation and the graph of its corresponding transitive closure.
Expressiveness of SETAFs and support-free ADFs under 3-valued semantics
Published in Journal of Applied Non-Classical Logics, 2023
W. Dvořák, A. Keshavarzi Zafarghandi, S. Woltran
An interpretationv (for F) is a function , that maps arguments to one of the three truth values true (), false () or undecided (). Truth values can be ordered via information ordering relation given by and and no other pair of truth values are related by . Relation is the reflexive and transitive closure of . An interpretation v is two-valued if it maps each argument to either or . Let be the set of all interpretations for an ADF D. Then, we call a subset of all interpretations of the ADF, , an interpretation set. Interpretations can be ordered via with respect to their information content, i.e. if for each . Further, we denote the update of an interpretation v with a truth value for an argument b by , i.e. and for . Finally, the partial valuation of acceptance condition by v, is given by , for .