Search

Multivariate extreme value distributions are a common choice for modeling multivariate extremes. In high dimensions, however, the construction of flexible and parsimonious models is challenging. We propose to combine bivariate max‐stable distributions into a Markov random field with respect to a tree. Although in general not max‐stable itself, this Markov tree is attracted by a multivariate max‐stable distribution. The latter serves as a tree‐based approximation to an unknown max‐stable distribution with the given bivariate distributions as margins. Given data, we learn an appropriate tree structure by Prim's algorithm with estimated pairwise upper tail dependence coefficients as edge weights. The distributions of pairs of connected variables can be fitted in various ways. The resulting tree‐structured max‐stable distribution allows for inference on rare event probabilities, as illustrated on river discharge data from the upper Danube basin. [ABSTRACT FROM AUTHOR]

Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios, often requiring intricate algorithmic design and exponential time. Recently, there has been growing interest in end-to-end deep neural networks for solving routing problems. However, such methods typically produce sequences of vertices, which make it difficult to apply them to general combinatorial optimization problems where the solution set consists of edges, as in various spanning tree problems. In this paper, we propose NeuroPrim, a novel framework for solving various spanning tree problems by defining a Markov decision process for general combinatorial optimization problems on graphs. Our approach reduces the action and state space using Prim's algorithm and trains the resulting model using REINFORCE. We apply our framework to three difficult problems on the Euclidean space: the degree-constrained minimum spanning tree problem, the minimum routing cost spanning tree problem and the Steiner tree problem in graphs. Experimental results on literature instances demonstrate that our model outperforms strong heuristics and achieves small optimality gaps of up to 250 vertices. Additionally, we find that our model has strong generalization ability with no significant degradation observed on problem instances as large as 1,000. Our results suggest that our framework can be effective for solving a wide range of combinatorial optimization problems beyond spanning tree problems. [ABSTRACT FROM AUTHOR]

Wireless sensor networks (WSNs) are important for applications like environmental monitoring and industrial automation. However, the limited energy resources of sensor nodes pose a significant challenge to the network’s longevity. Energy imbalances among nodes often result in premature failures and reduced overall network lifespan. Current solutions have not adequately addressed this issue due to network dynamics, varying energy consumption rates, and uneven node distribution. To tackle this, we propose a novel method using Prim’s algorithm to construct minimum spanning trees (MSTs) that enhance energy balance in WSNs. Prim’s algorithm effectively identifies optimal connections among network nodes to minimize energy consumption. Our methodology includes several key steps: network initialization, energy consumption modeling, MST construction using Prim’s algorithm, and optimizing the movement of mobile sink nodes. Extensive experiments with diverse datasets show that our approach significantly improves energy equilibrium, demonstrating high sensitivity and moderate complexity. This research underscores the potential of Prim’s algorithm to extend the lifespan of WSNs and enhance energy efficiency, contributing to sustainable and effective network deployments.

This work presents a specialized tabu search algorithm applied to the problem of electric power distribution systems primary feeders’ reconfiguration. The specialization is related to two fundamental aspects of the tabu search algorithm. The first proposal eliminates the concept of a list of prohibited attributes and the aspiration criterion, but also avoids the possibility of revisiting a candidate solution so that cycling is avoided by maintaining a tabu list with all previously visited solutions. The second proposal is the possibility of restarting the search from the incumbent solution while avoiding paths that can be formed by revisiting candidate solutions. A new strategy based on Prim’s algorithm generates a high-quality initial solution for the problem. Tests are conducted using the 33-, 84-, 118-, 136-, and 415-node test systems. The results demonstrate the effectiveness of the proposal for solving the reconfiguration problem since the best-known solution for each system is achieved within highly efficient execution times.

The minimum spanning tree problem (MSTP) revolves around creating a spanning tree (ST) within a graph/network that incurs the least cost compared to all other potential STs. This represents a vital and fundamental issue in the realm of combinational optimization problems (COP). Supply chain management, communication, transportation, and routing are a few examples of real-world issues that have been represented using the MSTP. Uncertainties exist in almost every real life application of MSTP due to inconsistency, improperness, incompleteness, vagueness and indeterminacy of the information and It generates really challenging scenarios to determine the arc length precisely. The main motivation behind this research work is to design a method for MST which will be simple enough and effective in real world scenarios. Neutrosophic set (NS) is a well known renowned theory, which one can this type of uncertainty in the edge weights of the ST. In this article, we review trapezoid neutrosophic set/number to describe the arc weight of a neutrosophic network for MSTP. Here, we introduce an algorithm for solving MSTP in neutrosophic environment. In our proposed method, we describe the uncertainties in Prim’s algorithm for MSTP using trapezoid neutrosophic set as edge cost. Here examples of numerical sets are used to explain the proposed algorithm.

Maze is a place that has many paths with tortuous paths that are misleading and full of dead ends and can be viewed as a grid graph. A non-perfect maze is a maze that has a cycle. This research produces an algorithm that can form a non-perfect maze with a size of m×n which has two types of bias. The first bias is the composition of the percentage of horizontal and vertical partitions. The second bias is the percentage of the number of cycles. The algorithm created in this study was generated by modifying Prim’s algorithm and the use of Fisher-Yates algorithm which is used in random selection in Prim’s algorithm. The non-perfect maze algorithm begins with the calculation of the parameter values of the two types of bias and continues with forming a perfect maze and ends with forming a non-perfect maze. The algorithm that has been designed can form a non-perfect maze with a complexity of O(|E|^2), where E is the set of edges of an m×n grid graph. Flash-based application development is also carried out in order to implement algorithms to obtain a non-perfect maze. The non-perfect maze is produced in a two-dimensional visual form in the form of an image along with its corresponding grid graph. The application is capable of displaying up to the first 20 solutions of the biased maze.

The displacement of a sensor node on the human body to monitor the internal changes of human is an emerging technology. The Internet of Medical Things (IoMT) reduces an individual's fatal problems. Hence, this paper presents the routing protocol for wireless body area network (WBAN) based on thermal and link quality and low-cost transmission. First, the number of paths is discovered based on the link quality and the thermal effect to transmit the sensed data by the IoMT device. All those evolved paths are optimized based on the cost for transmission; the prim's algorithm achieves this. The price for all paths achieved by the prim's algorithm is stored in the prim table, which will reduce the computation complexity and time. This two-stage process makes the proposed routing algorithm adaptive, hence the name Prim Based Link Quality and Thermal Aware Adaptive Routing (PLTAAR) protocol. Due to the focus on link quality, the energy utilized by the biosensor node for the retransmission of data queuing is reduced, and the thermal aware consideration protects the human from radiation effects caused by the IoMT devices. The proposed system model for the medical service is implemented on MATLAB. [ABSTRACT FROM AUTHOR]

The recent trends in the development of power systems are focused on the Self-Healing Grid technology fusing renewable energy sources. In the event of a failure of the power system, automated distribution grids should continue to supply energy to consumers. Unfortunately, there are currently a limited number of algorithms for rebuilding a power system with renewable energy sources. This problem is possible to solve by implementing restoration algorithms based on graph theory. This article presents the new modification of Prim's algorithm, which has been adapted to operate on a power grid containing several power sources, including renewable energy sources. This solution is unique because Prim's algorithm is ultimately dedicated to single-source graph topologies, while the proposed solution is adapted to multi-source topologies. In the algorithm, the power system is modeled by the adjacency matrices. The adjacency matrixes for the considered undirected graphs are symmetric. The novel logic is based on the original method of determining weights depending on active power, reactive power and active power losses. The developed solution was verified by performing a simulation on a test model of the distribution grid powered by a renewable energy source. The control logic concept was compared with the reference algorithms, which were chosen from the ideas representing available approaches based on graph theory present in the scientific publications. The conducted research confirmed the effectiveness and validity of the novel restoration strategy. The presented algorithm may be applied as a restoration logic dedicated to power distribution systems. [ABSTRACT FROM AUTHOR]

Self-healing grids are one of the most developing concepts applied in electrical engineering. Each restoration strategy requires advanced algorithms responsible for the creation of local power systems. Multi-agent automation solutions dedicated for smart grids are mostly based on Prim's algorithm. Graph theory in that field also leaves many problems unsolved. This paper is focused on a variation of Prim's algorithm utility for a multi-sourced power system topology. The logic described in the paper is a novel concept combined with a proposal of a multi-parametrized weight calculation formula representing transmission features of energy delivered to loads present in a considered grid. The weight is expressed as the combination of three elements: real power, reactive power, and real power losses. The proposal of a novel algorithm was verified in a simulation model of a power system. The new restoration logic was compared with the proposal of the strategy presented in other recently published articles. The novel concept of restoration strategy dedicated to multi-sourced power systems was verified positively by simulations. The proposed solution proved its usefulness and applicability. [ABSTRACT FROM AUTHOR]

Self-healing grids are one of the most developing concepts applied in electrical engineering. Each restoration strategy requires advanced algorithms responsible for the creation of local power systems. Multi-agent automation solutions dedicated for smart grids are mostly based on Prim’s algorithm. Graph theory in that field also leaves many problems unsolved. This paper is focused on a variation of Prim’s algorithm utility for a multi-sourced power system topology. The logic described in the paper is a novel concept combined with a proposal of a multi-parametrized weight calculation formula representing transmission features of energy delivered to loads present in a considered grid. The weight is expressed as the combination of three elements: real power, reactive power, and real power losses. The proposal of a novel algorithm was verified in a simulation model of a power system. The new restoration logic was compared with the proposal of the strategy presented in other recently published articles. The novel concept of restoration strategy dedicated to multi-sourced power systems was verified positively by simulations. The proposed solution proved its usefulness and applicability.

Reliability improvement of power distribution systems is a pre-request for economic and social development of any country. Currently, there is a rapid growth of industrial, commercial, residential and other service supplying institutions. All of these institutions need reliable power supply. Due to this, utilities must work hard and ensure that the customers are getting a reliable power supply. However, higher power interruption frequency and longer interruption duration are the most serious problem facing Ethiopian power distribution systems and this problem affects the daily activity of customers. In this paper, smart grid technology applications using optimal placement of switching/automating devices, network reconfiguration and rapid power restoration is performed to improve the reliability problem of Bahir Dar power distribution system. Optimal placement of switching/automating devices and network reconfiguration is determined by the Genetic Algorithm optimization technique using mat lab software. The rapid power restoration is carried out by Prim‘s Algorithm used for constructing the Minimum Spanning Tree in mat lab software. The study is tested at Bata the 34 bus feeder of Bahir Dar distribution system. The existing network is assessed and the reliability indices such as SAIFI, SAIDI, ASAI, CAIDI and EENS are evaluated using ETAP 12.6.0 software.

The recent trends in the development of power systems are focused on the Self-Healing Grid technology fusing renewable energy sources. In the event of a failure of the power system, automated distribution grids should continue to supply energy to consumers. Unfortunately, there are currently a limited number of algorithms for rebuilding a power system with renewable energy sources. This problem is possible to solve by implementing restoration algorithms based on graph theory. This article presents the new modification of Prim’s algorithm, which has been adapted to operate on a power grid containing several power sources, including renewable energy sources. This solution is unique because Prim’s algorithm is ultimately dedicated to single-source graph topologies, while the proposed solution is adapted to multi-source topologies. In the algorithm, the power system is modeled by the adjacency matrices. The adjacency matrixes for the considered undirected graphs are symmetric. The novel logic is based on the original method of determining weights depending on active power, reactive power and active power losses. The developed solution was verified by performing a simulation on a test model of the distribution grid powered by a renewable energy source. The control logic concept was compared with the reference algorithms, which were chosen from the ideas representing available approaches based on graph theory present in the scientific publications. The conducted research confirmed the effectiveness and validity of the novel restoration strategy. The presented algorithm may be applied as a restoration logic dedicated to power distribution systems.

Prim's algorithm has demonstrated a very effective and selective method of solving the minimum spanning tree optimization problems. It is a greedy algorithm that starts from an empty spanning tree and reaches its goal by picking the minimum weight edges which alternately optimizes the path in less possible time. In this paper, the capability of prim's algorithm in designing the behavioural controller of a humanoid robot has been shown. Here, a new hybrid PA–Fuzzy motion planning approach has been proposed that uses the concept of minimizing the distance between the robot and obstacles as well as robot and target. An optimal turning angle is generated by the hybrid controller that helps to avoid the obstacles present in the arena to create a collision-free path. The results obtained from hybrid PA–Fuzzy motion planning procedure show the capability of the controller in achieving the optimal paths in different environments with both static and dynamic obstacles. The results observed from simulation and experimental arenas are found to be in satisfactory agreement with each other producing minimal error limits. The developed hybrid technique is compared with some existing methodologies, and significant improvement is found in relation to path length and computational time. [ABSTRACT FROM AUTHOR]

We derive cutting planes for cardinality-constrained linear programs. These inequalities can be used to separate any basic feasible solution of an LP relaxation of the problem, assuming that this solution violates the cardinality requirement. To derive them, we first relax the given simplex tableau into a disjunctive set, expressed in the space of nonbasic variables. We establish that coefficients of valid inequalities for the closed convex hull of this set obey ratios that can be computed directly from the simplex tableau. We show that a transportation problem can be used to separate these inequalities. We then give a constructive procedure to generate violated facet-defining inequalities for the closed convex hull of the disjunctive set using a variant of Prim's algorithm. [ABSTRACT FROM AUTHOR]

The radio resource allocation in wireless communication is analysed in this paper. Pair of users communicates each other through multiple two way relays in orthogonal frequency division multiplexing transmission systems. The total throughput is maximized by relay selection, channel and relay assignment, subcarrier pairing and subcarrier allocation by prim’s algorithm. The graphical theory approach has used to solve the problem optimally in polynomial time. The evaluation of the network total throughput with respect to transmit power node and the number of relay nodes are analysed through simulation. In this work, the improvement in sum rate with optimum carrier assignment using proposed algorithm is demonstrated against the classical work.

Cancer occurs because of an anomaly in cell structure due to the uncontrolled behavior of genes. The approach to reduce and identify the set of dominant biomarkers for malfunctioning genes which may lead to various types of cancer has been identified. A reduced Gene Prediction Graph depicting the dominant genes along with the extent of their interdependence is plotted both for a healthy person and a diseased individual. The genes are ranked with decreasing order of relevance. A detailed comparative study between the graphs detects the set of malfunctioning genes with decreasing order of influence. The theory of Information Gain, Fuzzy Logic, Graph theory-based Algorithm, Entropy, and Symmetric Uncertainty has been applied in the development of the proposed model named as Entropy-based fuzzy hybrid framework for gene prediction network. The entire algorithm is demonstrated in fuzzy framework of gene expression datasets. A detailed comparative study has been done with some of the existing methodologies, viz., Support Vector Machine approach based on Recursive Feature Elimination, Hidden Markov Model, Gaussian Mixture Model, Fuzzy Composite Association Rule Mining, Frequent Pattern-Growth, Apriori. The performance of the methodology has been demonstrated on the lung adenocarcinoma datasets. The results are appropriately validated using top 100 genes of National Center for Biotechnology Information database, for finding out the true positives. [ABSTRACT FROM AUTHOR]

In self-healing grid systems, high utility in the use of greedy algorithms is observed. One of the most popular solutions is based on Prim’s algorithm. In the computation, the power grid is represented as a weighted graph. This paper presents a few possibilities of calculation of the numerical weight of a branch of the graph. The proposition of a modified edge weight calculation based on active power belongs to this group. The other solutions are novel subalgorithms bounded by real power, reactive power, and normalized factor. This factor is a mathematical combination of active and reactive power multiplied by influence coefficients. Requirements necessary for a power system are applied in the considered algorithms. Each of these proposed algorithms includes the power source limits, voltage level at busbars, and power system transmission features, such as transmission lines rated currents and power losses. All mentioned methods were compiled into separate algorithms, which can be used to compute graph model parameters. A simulation model based on Prim’s algorithm was prepared to compare the suitability of presented concepts. All weights of the subalgorithms were compared to each other. That is why different power system restoration strategies may require various methods of calculating weights of the graph’s branches.

Bauman Moscow State Technical University is implementing a project to develop operating principles of computer system having radically new architecture. A developed working model of the system allowed us to evaluate an efficiency of developed hardware and software. The experimental results presented in previous studies, as well as the analysis of operating principles of new computer system permit to draw conclusions regarding its efficiency in solving discrete optimization problems related to processing of sets.The new architecture is based on a direct hardware support of operations of discrete mathematics, which is reflected in using the special facilities for processing of sets and data structures. Within the framework of the project a special device was designed, i.e. a structure processor (SP), which improved the performance, without limiting the scope of applications of such a computer system.The previous works presented the basic principles of the computational process organization in MISD (Multiple Instructions, Single Data) system, showed the structure and features of the structure processor and the general principles to solve discrete optimization problems on graphs.This paper examines two search algorithms of the minimum spanning tree, namely Kruskal's and Prim's algorithms. It studies the implementations of algorithms for two SP operation modes: coprocessor mode and MISD one. The paper presents results of experimental comparison of MISD system performance in coprocessor mode with mainframes.

For a Support Vector Machine (SVM) algorithm, the time required for classifying an unknown data point is proportional to the number of support vectors. For some real time applications, use of SVM could be a problem if the number of support vectors is high. Depending on the complexity of the class structure, sometimes the number of support vectors of a SVM model increases with the number of training data points. Here our objective is to reduce the number of support vectors, yet, maintaining more of less the same level of accuracy as that of a normal SVM that does not use any reduction of support vectors. An SVM finds a separating hyperplane maximizing the margin of separation and hence, the location of the hyperplane is primarily dependent on a set of “boundary points”. Here, we first identify some boundary points using a minimum spanning tree on the training data to obtain a reduced training set. The SVM algorithm is then applied on the reduced training data to generate the classification model. We call this algorithm, Minimally Spanned Support Vector Machine (MS-SVM). We also assess the performance by relaxing the definition of boundary points. Moreover we extend the algorithm to a feature space using a kernel transformation. In this case, an MST is generated in the feature space using the associated kernel matrix. Our experimental results demonstrate that the proposed algorithm can considerably reduce the number of support vectors without affecting the overall classification accuracy. This is true irrespective of whether the MST is generated in the input space or in the feature space. Thus the MS-SVM algorithm can be used instead of SVM for efficient classification. [ABSTRACT FROM AUTHOR]

This paper develops a greedy heuristic for the capacitated minimum spanning tree problem (CMSTP), based on the two widely known methods of Prim and of Esau-Williams. The proposed algorithm intertwines two-stages: an enhanced combination of the Prim and Esau-Williams approaches via augmented and synthetic node selection criteria, and an increase of the feasible solution space by perturbing the input data using the law of cosines. Computational tests on benchmark problems show that the new heuristic provides extremely good performance results for the CMSTP, justifying its effectiveness and robustness. Furthermore, excluding the feasible space expansion, we show that we can still obtain good quality solutions in very short computational times. [ABSTRACT FROM AUTHOR]

This paper presents a visualization tool that works as a debugger to learn the minimal spanning tree. The tool allows the user to enter the graph as a matrix and then enable the user to visualize the execution of the algorithm step by step. During the visualization, the tool can handle and debug the errors that occurred by the user. Also, the tool gives the user feedback from the execution of the algorithm by storing the errors that occurred by the user. The teacher and students can use the tool inside and outside the class. The tool was evaluated by the students, and the results show that the tool enhances the understanding of algorithms. [ABSTRACT FROM AUTHOR]

En este trabajo se presenta un nuevo algoritmo que permite reconfigurar un sistema de distribución (SD) de energía eléctrica minimizando la energía no suministrada (ENS). El SD se modela utilizando teoría de grafos, mientras que la ENS se formula recursivamente y se parametriza en términos de los índices de confiabilidad del SD. Empleando esta modelación se transforma el problema de optimización en el problema de encontrar el árbol de mínima expansión (AME) a partir del grafo que modela al SD, donde la métrica de distancia utilizada corresponde a la ENS a cada nodo del SD. Para encontrar de manera eficiente el AME se utiliza el algoritmo de Prim, ya que pertenece a la clase de algoritmos voraces en el cálculo del AME. Adicionalmente, se propone un algoritmo que realiza una revisión del AME obtenido analizando las topologías que fueron descartadas aleatoriamente durante el proceso de decisión. El desempeño del algoritmo de optimización se evalúa en sistemas de pruebas y en dos sistemas eléctricos reales.This paper presents a novel algorithm to reconfigure an electric power distribution network (EPDN), minimizing its non-supplied energy (NSE). The EPDN is modeled using graph theory and the NSE is recursively formulated in terms of the reliability parameters of the EPDN. Based on this mathematical model, we transform the original optimization problem into the graph theory problem of finding the minimum spanning tree (MST) of a given graph, which models the EPDN. The distance metric employed by the searching algorithm is the NSE. In order to efficiently find the MST, Prim's algorithm is employed due to is greedy search behavior. In addition, a backtracking algorithm is used to check the MST obtained. The backtracking algorithm analyzes all the candidate topologies that were randomly discarded during the decision process. The performance of the optimization algorithm is evaluated using testing systems and two actual EPDNs.

We revisit the discrete additive and multiplicative coalescents, starting with n particles with unit mass. These cases are known to be related to some 'combinatorial coalescent processes': a time reversal of a fragmentation of Cayley trees or a parking scheme in the additive case, and the random graph process $$(G(n,p))_p$$ in the multiplicative case. Time being fixed, encoding these combinatorial objects in real-valued processes indexed by the line is the key to describing the asymptotic behaviour of the masses as $$n\rightarrow +\infty $$ . We propose to use the Prim order on the vertices instead of the classical breadth-first (or depth-first) traversal to encode the combinatorial coalescent processes. In the additive case, this yields interesting connections between the different representations of the process. In the multiplicative case, it allows one to answer to a stronger version of an open question of Aldous (Ann Probab 25:812-854, 1997): we prove that not only the sequence of (rescaled) masses, seen as a process indexed by the time $$\lambda $$ , converges in distribution to the reordered sequence of lengths of the excursions above the current minimum of a Brownian motion with parabolic drift $$(B_t+\lambda t - t^2/2, t\ge 0)$$ , but we also construct a version of the standard augmented multiplicative coalescent of Bhamidi et al. (Probab Theory Relat, 2013) using an additional Poisson point process. [ABSTRACT FROM AUTHOR]

Several nonparametric methods are available in the literature to test the independence between two random vectors. But, many of them perform poorly for high dimensional data and are not applicable when the dimension of one of these vectors exceeds the sample size. Moreover, most of these tests are not distribution-free in the general multivariate set up. Recently, Heller et al. (2012) proposed a test of independence, which is distribution-free and can be conveniently used even when the dimensions are larger than the sample size. In this article, we point out some limitations of this test and propose some modifications to overcome them retaining its distribution-free property. Some simulated and real data sets are analyzed to demonstrate the utility of our proposed modifications. [ABSTRACT FROM AUTHOR]