China
Africa
Explore chapters and articles related to this topic
Saliency Object Detection
Published in Yu-Jin Zhang, A Selection of Image Analysis Techniques, 2023
In this method, the image is simply represented as a minimum spanning tree (MST). The minimum spanning tree is a tree structure that can be transformed from a connected graph. Generally, an image is first represented as a 4-adjacent undirected graph (where the node corresponds to the pixel and the arc represents the grayscale difference between the pixels), and then the minimum spanning tree of the image can be obtained by eliminating the arcs with large values/weights. The minimum spanning tree of a graph with N nodes still contains the original N nodes, and retains the fewest arcs that make the graph connected, so that the path between pixels is unique (Tu et al. 2016). It is easier to search for the path with the smallest distance value in this minimum spanning tree, because the search range is much smaller. In practice, the minimum fence distance can be calculated efficiently and quickly by traversing the tree twice. First traverse once from the leaves to the root, and then traverse once from the root to the leaves.
Basic Data Structures
Published in Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar, Handbook of Algorithms for Physical Design Automation, 2008
The usual approach for constructing a minimum spanning tree is to first define a complete weighted graph on the set of points and then to construct a spanning tree on it, for example, by running Kruskal’s algorithm (see Chapter 5). Given a set of points V, an undirected graph G = (V, E) is called a spanning graph if it contains a minimum spanning tree. The cardinality of a graph is its number of edges. The complete graph has a cardinality of Θ(n2), which is expensive. For the L2 metric, the Delaunay triangulation, a spanning graph of cardinality O(n), can be constructed in Θ(n log n) time. However, this approach does not work for the L1 metric as the Delaunay triangulation may be degenerate. Zhou et al. [9] describe a rectilinear spanning graph of cardinality O(n) that can be constructed in O(n log n) time [9]. Its use in the construction of a Steiner tree is described in Ref. [10]. We sketch the salient features of this data structure below.
Dominating tree problem heuristics for scale-free networks
Published in Shin-ya Nishizaki, Masayuki Numao, Jaime Caro, Merlin Teodosia Suarez, Theory and Practice of Computation, 2019
K.P. Urog, J.Y. Bantang, H.N. Adorna
Moreover, most algorithms for solving DTP of a graph start with the idea behind Kruskal’s algorithm, where one computes all shortest paths between nodes before optimizing these shortest path information between nodes. This actually makes sense because of the edge minimization objective of the DTP. Kruskal’s algorithm finds an edge of the least possible weight that connects any two trees in the forest to create a minimum-spanning-tree. This ensures that the resulting DT is of the minimum edge-cost.
A dynamic heuristic for WSNs routing
Published in Cogent Engineering, 2021
In our approach, we will use the PRIM’s algorithm for routing data. Thus, PRIM’s algorithm (Figure 2) provides the minimum spanning tree of a graph. Assume an undirected connected graph. A spanning tree of that graph would be a subgraph that connects all the vertices of that tree. A single graph can have many spanning trees. If some weights (energy in our case) are assigned to each edge, then the MST is the spanning tree with weight less than any other spanning tree of that graph. A graph is shown in Figure 1, weights are assigned to each of its branches. As can be seen, the highlighted tree is known as the spanning tree. Many other spanning trees can also be built by connecting the vertices of the given figure in different ways. The routing algorithm in our approach can be described as follows: We consider a weighted connected graph G with n vertices. Prim’s algorithm finds a minimum spanning tree of G.
Review on Petri Net Modeling and Analysis of a Smartphone Manufacturing System
Published in Cogent Engineering, 2020
Yi-Nan Lin, Tsang-Yen Hsieh, Cheng-Ying Yang, Victor R.L. Shen, Tony Tong-Ying Juang, Ting-Jui Huang
The algorithm of minimum spanning tree (MST) can be used for cost optimization. A well-known one is called the Prim algorithm, which is used to find a representative shortest path. It divides all vertices into two groups. The first group is a set of vertices S in which the shortest path has been found, and the second group is a set of vertices U which is remaining undetermined shortest paths. According to the shortest path, the second set of vertices is added to S in the order from small weight to large weight. Until all vertices join S, it means that the vertices are all connected.
Cost allocation rule of minimum spanning tree problems without a supplier
Published in Systems Science & Control Engineering, 2020
Jia-quan Zhan, Hao Cheng, Zhen-sen Zhang
A tree is a connected and acyclic graph. If a spanning subgraph of graph G is a tree, then this tree is said to be a spanning tree of graph G. Given a connected graph G = (V, E) in which each edge has a nonnegative weight, a spanning tree of graph G is said to be a minimum spanning tree of graph G if it has the minimum weight among all spanning trees.