Search

For the layout problem of rural highway network, which is often characterized by a cluster of geographically dispersed nodes, neither the Prim algorithm nor the Kruskal algorithm can be readily applied, because the calculating speed and accuracy are by no means satisfactory. Rather than these two polynomial algorithms and the traditional genetic algorithm, this paper proposes an improved genetic algorithm. It encodes the minimum spanning trees of large-scale rural highway network layout with Prufer array, a method which can reduce the length of chromosome; it decodes Prufer array by using an efficient algorithm with time complexityo(n)and adopting the single transposition method and orthoposition exchange method, substitutes for traditional crossover and mutation operations, which can effectively overcome the prematurity of genetic algorithm. Computer simulation tests and case study confirm that the improved genetic algorithm is better than the traditional one.

This paper presents a simple and efficient near optimal algorithm, named Maximum Adjacent Minimum degree Algorithm (MAMA) for optimization of minimum vertex cover problem. The proposed algorithm at each step add that maximum degree vertex which is adjacent to minimum degree vertex. The computational complexity and optimality comparison are carried with other state of the art algorithms on small benchmark instances as well as on large benchmark instances to check the efficiency of the proposed algorithm. The proposed algorithm outperforms the other well-known algorithm and returns near optimal result in quick time.

In real life, we always want to reach our goal in minimum effort, it should have a minimum constrained path. The path may be shortest route in practical, either physical or electronic medium, or the minimum costing path in term of resources. The idea is to represent the problem as a graph and finding a spanning tree with specific design criteria. Here, we have chosen a minimum degree spanning tree, which can be generated in real time with minimum turnaround time [11]. The solution approach, in general, is approximate. We have used a heuristic approach, namely hybrid modified genetic algorithm (HMGA), with motivated criteria of encoded data structures of graph. We compare the experimental result with the existing approximate algorithms and the results are very promising.

In the network operation stage of urban mass transit, the connection relations between lines can effectively improve travel accessibility. As the last opportunity to travel on the same day, whether the last train can achieve transfer will directly affect passengers&rsquo, travel experiences. It is an important work to make the connection scheme of the last train, which needs to take the network structure, the trend, and the volume of passenger flow into overall consideration. This paper analyzes the characters of the last train connection, including the connection structure and the accessible form. Then, we establish a scheme model and define the objectives, the constraints, and the decision data source, and transform it into a graph theory problem. Taking an urban mass transit network as an example, we demonstrate the solution process by using an improved Prim algorithm. Finally, the main aspects and methods of initial scheme optimization are proposed.

This paper proposes a three-layer model to find the optimal routing of an underground electrical distribution system, employing the PRIM algorithm as a graph search heuristic. In the algorithm, the first layer handles transformer allocation and medium voltage network routing, the second layer deploys the low voltage network routing and transformer sizing, while the third presents a method to allocate distributed energy resources in an electric distribution system. The proposed algorithm routes an electrical distribution network in a georeferenced area, taking into account the characteristics of the terrain, such as streets or intersections, and scenarios without squared streets. Moreover, the algorithm copes with scalability characteristics, allowing the addition of loads with time. The model analysis discovers that the algorithm reaches a node connectivity of 100%, satisfies the planned distance constraints, and accomplishes the optimal solution of underground routing in a distribution electrical network applied in a georeferenced area. Simulating the electrical distribution network tests that the voltage drop is less than 2% in the farthest node.

Given an undirected, connected and edge-weighted graph, the dominating tree problem (DTP) seeks on this graph a tree with minimum total edge weight such that each vertex of the graph is either in this tree or adjacent to a vertex in this tree. The DTP is a NP-Hard problem. In the literature only two heuristics for this problem are proposed so far in spite of the fact that it has several practical applications in the field of wireless sensor networks. In this paper, we propose one heuristic and two swarm intelligence techniques, viz. an artificial bee colony algorithm and an ant colony optimization algorithm for the DTP. Computational results show the effectiveness of our approaches.

The bounded diameter minimum spanning tree (BDMST) problem aims at finding the minimum weight spanning tree subject to a predefined diameter constraint. Due to the NP-hardness of the BDMST problem, several heuristic and meta-heuristic approaches have been proposed to find a near optimal solution in a reasonable time. In this article, a distributed algorithm is proposed for solving the BDMST problem based on learning automata. Generally, the proposed algorithm consists of two main phases. In the former phase, the proposed algorithm forms the action-set of learning automata and paths from the root to every other node. The latter phase constructs different spanning trees until it finds the optimum one. To show the performance of the proposed algorithm, it is compared with one of the well-known methods. Experimental results confirm the superiority of the proposed algorithm both in terms of the computational complexity and the weight of the spanning tree.

The graph vertices design into classes, for each vertex in the design of the abscissa, ordinate and in-degree members, realizes the dynamic demonstration minimum spanning tree. Dynamic visualize Prime algorithm and kruskal algorithm implementation process. Around two window synchronization of animation, " in order to find the minimum edge " list box list the minimum edge of a minimum spanning tree ,with thick line in the left window drawing the found minimum edge and On the edge of the vertex, in the right box demo the process of algorithm dynamic execution.

In k-means clustering algorithm, it remains a problem that the initial cluster centers are selected randomly. To deal with the randomness problem, the Prim minimum spanning tree is introduced to the initial center selection of K-means clustering algorithm. Firstly, the prim method is used to find the minimum spanning tree for the randomly generated points, then a group of points are selected as the initial center which has the maximum sum of the weights and all weights have little difference. Finally, we propose an improved K-means clustering algorithm based on prim. Simulation results show that, compared with NKM (Normal K-Means) algorithm, our algorithm improves the accuracy and reduces the data iterations.

In reference to international regional sewage pipe network and sewage treatment plant planning, the actual situation of China's villages and small town was investigated. According to the costs data from presented sewage pipe and sewage treatment plant construction system, the model on the sewage pipe network and sewage treatment plant charge was obtained. Then the model was simplified to be calculating the shortest distance between the wastewater treatment plant and the effluent discharge point. The suitable computing method for the shortest distance is building the minimum spanning tree. The software for computing was written with prim algorithm. The computing results can be used as a planning and design reference of sewage pipe network. The model method can be used for design program to select long-distance transmission or local treatment of the sewage.

In many real world problems related to weighted graphs, the input data corresponding to the weights are often imprecise due to incomplete or non-obtainable information. Finding the minimum spanning tree of such type of connected graphs is a challenge. This paper is introduced to find minimum spanning tree on a connected graph where the edges have rough weights.

The adjacent only quadratic minimum spanning tree problem is an NP-hard version of the minimum spanning tree where the costs of interaction effects between every pair of adjacent edges are included in the objective function. This paper addresses the biobjective version of this problem. A Pareto local search algorithm is proposed. The algorithm is applied to a set of 108 benchmark instances. The results are compared to the optimal Pareto front generated by a branch and bound algorithm, which is a multiobjective adaptation of a well known algorithm for the mono-objective case.

This paper suggests a method to reduce the number of performances of Kruskal and Reverse-delete algorithms. Present Kruskal and Reverse-delete algorithms verify whether the cycle occurs within the edges of the graph. For this reason, they have problems of unnecessarily performing extra algorithms from the edges, even though they`ve already obtained the minimum spanning tree. This paper, first of all, suggests the 1st method which reduces the no. of performances by introducing stop point criteria of algorithm, but at the same time, performs algorithms from all the edges, just like how Kruskal and Reverse-delete algorithms. Next, it suggests the 2nd method which finds the minimum spanning tree from the remaining edges after getting rid of all the unnecessary edges which are considered not to affect the minimum spanning tree. These suggested methods have an effect of terminating algorithm at least 1.4 times and at most 3.86times than Kruskal and Reverse-delete algorithms, when applied to the real graphs. We have found that the 2nd method of the Reverse-delete algorithm has the fastest speed in terminating an algorithm, among 4 algorithms which are results of the 2 suggested methods being applied to 2 algorithms.

An inverse minimum spanning tree problem makes the least modification on the edge weights such that a predetermined spanning tree is a minimum spanning tree with respect to the new edge weights. In this paper, the concept of uncertain α-minimum spanning tree is initiated for minimum spanning tree problem with uncertain edge weights. Using different decision criteria, two uncertain programming models are presented to formulate a specific inverse minimum spanning tree problem with uncertain edge weights involving a sum-type model and a minimax-type model. By means of the operational law of independent uncertain variables, the two uncertain programming models are transformed to their equivalent deterministic models which can be solved by classic optimization methods. Finally, some numerical examples on a traffic network reconstruction problem are put forward to illustrate the effectiveness of the proposed models.

Given weighted graph  , the minimum cut problem is classified with source  and sink  or without  and  . Given undirected weighted graph without  and  , Stoer-Wagner algorithm is most popular. This algorithm fixes arbitrary vertex, and arranges maximum adjacency (MA)-ordering. In the last, the sum of weights of the incident edges for last ordered vertex is computed by cut value, and the last 2 vertices are merged. Therefore, this algorithm runs  times. Given graph with  and  , Ford-Fulkerson algorithm determines the bottleneck edges in the arbitrary augmenting path from  to  . If the augmenting path is no more exist, we determine the minimum cut value by combine the all of the bottleneck edges. This paper suggests minimum cut algorithm for undirected weighted graph with  and  . This algorithm suggests MA-merging and computes cut value simultaneously. This algorithm runs  times and successfully divides  into disjoint  and  sets on the basis of minimum cut, but the Stoer-Wagner is fails sometimes. The proposed algorithm runs more than Ford-Fulkerson algorithm, but finds the minimum cut value within

Degree-constrained minimum spanning tree problem is an NP-hard bicriteria combinatorial optimization problem seeking for the minimum weight spanning tree subject to an additional degree constraint on graph vertices. Due to the NP-hardness of the problem, heuristics are more promising approaches to find a near optimal solution in a reasonable time. This paper proposes a decentralized learning automata-based heuristic called LACT for approximating the DCMST problem. LACT is an iterative algorithm, and at each iteration a degree-constrained spanning tree is randomly constructed. Each vertex selects one of its incident edges and rewards it if its weight is not greater than the minimum weight seen so far and penalizes it otherwise. Therefore, the vertices learn how to locally connect them to the degree-constrained spanning tree through the minimum weight edge subject to the degree constraint. Based on the martingale theorem, the convergence of the proposed algorithm to the optimal solution is proved. Several simulation experiments are performed to examine the performance of the proposed algorithm on well-known Euclidean and non-Euclidean hard-to-solve problem instances. The obtained results are compared with those of best-known algorithms in terms of the solution quality and running time. From the results, it is observed that the proposed algorithm significantly outperforms the existing method.

We study the design of local algorithms for massive graphs. A local graph algorithm is one that finds a solution containing or near a given vertex without looking at the whole graph. We present a local clustering algorithm. Our algorithm finds a good cluster---a subset of vertices whose internal connections are significantly richer than its external connections---near a given vertex. The running time of our algorithm, when it finds a nonempty local cluster, is nearly linear in the size of the cluster it outputs. The running time of our algorithm also depends polylogarithmically on the size of the graph and polynomially on the conductance of the cluster it produces. Our clustering algorithm could be a useful primitive for handling massive graphs, such as social networks and web-graphs. As an application of this clustering algorithm, we present a partitioning algorithm that finds an approximate sparsest cut with nearly optimal balance. Our algorithm takes time nearly linear in the number edges of the graph....

Most of previous genetic algorithms for solving graph problems have used a vertex-based encoding. We proposed an edge encoding based new genetic algorithm using a spanning tree. Contrary to general edge-based encoding, a spanning tree-based encoding represents only feasible partitions. As a target problem, we adopted the MAX CUT problem, which is well known as a representative NP-hard problem, and examined the performance of the proposed genetic algorithm. The experiments on benchmark graphs are executed and compared with vertex-based encoding. Performance improvements of the spanning tree-based encoding on sparse graphs was observed.

The Binary Identification Problem for weighted trees asks for the minimum cost strategy (decision tree) for identifying a vertex in an edge weighted tree via testing edges. Each edge has assigned a different cost, to be paid for testing it. Testing an edge e reveals in which component of T−e lies the vertex to be identified. We give a complete characterization of the computational complexity of this problem with respect to both tree diameter and degree. In particular, we show that it is strongly NP-hard to compute a minimum cost decision tree for weighted trees of diameter at least 6, and for trees having degree three or more. For trees of diameter five or less, we give a polynomial time algorithm. Moreover, for the degree 2 case, we significantly improve the straightforward O(n3) dynamic programming approach, and provide an O(n2) time algorithm. Finally, this work contains the first approximate decision tree construction algorithm that breaks the barrier of factor logn.

The spanning star forest problem is an interesting algorithmic problem in combinatorial optimization and finds different applications. We generalize it into the spanning k-tree forest problem, which is to find a maximum spanning forest in which each tree component has a central vertex and other vertices in the component have distance at most k away from the central vertex. We show that this new problem can be approximated with ratio [Formula: see text] in polynomial time for both undirected and directed graphs. In the weighted distance model, a ½-approximation algorithm is presented for it.

Given an edge-weighted simple graph G, the minimum quadratic spanning tree problem consists in finding a spanning tree of G such that the sum of the weights of its edges plus the sum of the product of the weights of pairs of edges is minimum over all spanning trees of G. When the product of the weights of pairs of edges is calculated only for adjacent edges, the problem is called adjacent-only minimum quadratic spanning tree. This problem belongs to NP-hard. In this study we investigate the performance of a tabu search algorithm with ejection chain for the bi-objective version of this problem. An experiment with 168 instances is reported.

Ovaj rad se bavi minimalnim razapinjajućim stablima u težinskim grafovima. Na početku rada su dane neke općenite definicije grafova kako bi se tematika približila stablima. Nakon toga slijedi definicija stabla, zajedno sa svojstvima i pripadajućim dokazima. Opisan je pojam razapinjajućeg stabla u grafu, te nakon toga i minimalno i maksimalno razapinjajuće stablo u težinskom grafu. U radu su opisana dva algoritma pronalaženja minimalnog razapinjajućeg stabla nekog grafa. Za oba algoritma je dan opis, dokazana ispravnost, pseudokod, analiza složenosti i primjer. Na kraju, napravio sam programsku implementaciju oba algoritma. U radu su priloženi bitni dijelovi programa za obavljanje algoritma, kao i izlazni rezultati. This work deals with the minimum spanning trees of weighted graphs. In the beggining, there are some general graph definitions, to get thematically closer to tree graphs. After that, trees are defined, together with their characteristics and proofs. Spanning trees are defined, and after them, the minimum and maximum spanning trees are defined also. This work also describes two algorithms for finding a minimum spanning tree for a weighted graph. There is a description, proof of corectness, pseudocode, complexity analisys, and an example for both algorithms. In the end, I made software implementations for both algorithms. This work also includes vital parts of the program, as well as the output data.

Given a vertex-weighted undirected graph, to find the vertex cover of minimum weight is called minimum weight vertex cover problem (MWVCP). It is known as an NP-hard problem. In this paper, a fast heuristic for MWVCP is proposed. Our algorithm is based on a simple algorithm called “list-heuristic.” Experimenal results show that our algorithm calculates better solutions in shorter time than approximation algorithms for MWVCP.

Finding minimum spanning trees (MST) in various types of networks is a well-studied problem in theory and practical applications. A number of efficient algorithms have been already developed for this problem. In this paper we present an efficient algorithm, namely Edge Pruned Minimum Spanning Tree (EPMST) algorithm, which combines ideas from randomized selection, Kruskal's algorithm and Prim's algorithm. The algorithm has a superior performance relative to the best-known algorithms especially when the graph is not very sparse. Specifically, EPMST outperforms a recently devised efficient algorithm on a wide range of input graphs.

Sweep coverage plays an important role in many applications like data gathering, sensing coverage, and devices control, etc. In this paper, we deal with sweep coverage problem with multiple mobile sensors to periodically cover n targets in the surveillance region. We propose three constant-factor approximations, namely CycleSplit, CoCycle, and AugPrim, to minimize the longest trajectory length of mobile sensors under different scenarios respectively. CycleSplit deals with non-cooperative sweep coverage problem (NCSC), in which each mobile sensor works independently along different trajectory cycle. It has an approximation ratio of (5-\frac{2}{n-m+1}), which improves the best known approximation ratio of 5. CoCycle solves the cooperative sweep coverage problem (CSC), in which multiple sensors work together to cover $n$ targets. Its approximation ratio is 4, which outperforms the state-of-art best approximation ratio of 6. AugPrim is also a 6-approximation. It computes the sensor route for multi-sink sweep coverage problem (MSSC), where each sensor has to transmit the gathered data to one of the given sinks in each detection period. It implements the modified Prim algorithm and augment paths in turn according to the sink positions. AugPrim is the first approximation for sweep coverage problem with sinks. Finally, we provide various numerical experiments and comparisons with several previous work to validate the efficiency of our design.

Fibonaccijeva hrpa je varijanta hrpe, razvijena od strane Fredmana i Tarjana s ciljem poboljšanja Dijkstrinog algoritma najkraćeg puta. Fibonaccijeva hrpa je prva hrpa koja obavlja operacije ubacivanja i smanjivanja ključa u konstantnom amortiziranom vremenu, uz logaritamsko vrijeme brisanja elemenata. S obzirom na utjecaj Fibonaccijeve hrpe na računarstvo, ovaj rad se bavi opisom Fibonaccijeve hrpe i njenog utjecaja na kombinatornu optimizaciju. Provedena je analiza rada Dijkstrinog i Primovog algoritma s Fibonaccijevom hrpom u odnosu na druge moguće implementacije prioritetnog reda. Fibonacci heap is a variant of heap, developed by Fredman and Tarjan with the purpose of improving Dijkstra’s shortest path algorithm. Fibonacci heap is a first heap that accomplishes insert and decrease key operations in constant amortized time with logarithmic time for deleting the elements. Because of the importance of Fibonacci heap in the field of computer science, this work describes Fibonacci heap and its influence on the field of combinatorial optimization. Analysis on the influence of Fibonacci heaps in Dijkstra’s and Prim’s algorithms has been made, in respect to some other possible implementations of priority queue.

En este artículo se muestra la aplicación de una herramienta informática basada en teoría de grafos para analizar y resolver problemas de las rutas más cortas, utilizando los algoritmos de Prim, Kruskal y de búsqueda local de Tabú Search. Para el desarrollo de esta aplicación se utilizaron los siguientes elementos: Visual Studio 2010, librería GraphSharp y librería QuickGraph. Para la creación de esta herramienta, se estableció una estructura de clases que diera soporte a los gráficos: 1) PocGraph: representa el grafo; 2) PocEdge: representa las aristas del grafo; y 3) PocVertex: representa los nodos o vértices del grafo. Tanto el método de Kruskal como Prim generan un árbol mínimo recubridor del grafo, el cual consiste en un subgrafo del original. El algoritmo de Prim se trabajó con el objetivo de encontrar el árbol recubridor más corto; mientras que el algoritmo de Kruskal, con la finalidad de hallar el árbol minimal a partir de instancias TSP. El método de Tabú Search se aplica para encontrar el mínimo camino cerrado que une todos los vértices o nodos. Se diseñó el algoritmo de Tabú Search para minimizar las rutas partiendo de una solución inicial la cual se va modificando hasta obtener el resultado.

Distributed system has an inherent problem of unevenly distributed load. The possible solution to this problem is load balancing. For the above purpose it is very important to have updated information about the load status of the nodes comprising the system. This work proposes a Distributed Minimum Spanning Tree based Information Exchange (DMSTIE) strategy. The strategy helps in collecting the load information of the nodes through the edges formed during the Distributed Minimum Spanning Tree (DMST) process. Based on the information about the system state various load balancing approach can be applied for transferring extra load over the underutilized nodes. An MST based approach results in the information collection and eventually dispatch of load efficiently in terms of communication and computation.

We formally prove the correctness of Prim’s algorithm for computing minimum spanning trees. We introduce new generalisations of relation algebras and Kleene algebras, in which most of the proof can be carried out. Only a small part needs additional operations, for which we introduce a new algebraic structure. We instantiate these algebras by matrices over extended reals, which model the weighted graphs used in the algorithm. Many existing results from relation algebras and Kleene algebras generalise from the relation model to the weighted-graph model with no or small changes. The overall structure of the proof uses Hoare logic. All results are formally verified in Isabelle/HOL heavily using its integrated automated theorem provers.

A novel clustering method based on spectral clustering theory and spectral cut standard is proposed via analyzing the characteristics of short text and the defects of the existing clustering algorithms. First of all, a weighted undirected graph is created according to spectral clustering theory, similarity between node and node is calculated on graph, and a symmetrical documents similarity matrix is constructed, which provides all information for the clustering algorithm. Inspired by Greedy strategy, we utilize prim to develop PrimMAE algorithm for the purpose of partitioning graph into two parts, in which RMcut is termination condition of partitioning process, and then it is fed into CASC algorithm to cut the documents set iteratively. Ultimately, high quality clustering results demonstrate the effectiveness of the new clustering algorithm.

Efficient routing problem exists from several years. Spanning tree plays very important role to design routing algorithms efficiently. To obtain the minimum cost a minimum spanning tree is formed from the given graph. Greedy technique plays important role to generate minimum spanning tree. Several approaches exists to solve minimum spanning tree but in this paper a new methodology is designed and developed to find minimum spanning tree using subtraction and remainder procedure. This procedure also uses Greedy approach. The main objective is to present a new way to find minimum spanning tree. An example is also given to understand the procedure in efficient way.

The generalized minimum spanning tree problem consists of finding a minimum cost spanning tree in an undirected graph for which the vertices are divided into clusters. Such spanning tree includes only one vertex from each cluster. Despite the diverse practical applications for this problem, the NP-hardness continues to be a computational challenge. Good quality solutions for some instances of the problem have been found by combining specific heuristics or by including them within a metaheuristic. However studied combinations correspond to a subset of all possible combinations. In this study a technique based on a genotype-phenotype genetic algorithm to automatically construct new algorithms for the problem, which contain combinations of heuristics, is presented. The produced algorithms are competitive in terms of the quality of the solution obtained. This emerges from the comparison of the performance with problem-specific heuristics and with metaheuristic approaches.

In this paper, least-cost minimum spanning tree (LC-MST) problem is defined as a method to construct a minimum cost spanning tree that has the least-cost edges in the network by using the distance (cost) matrix. The paper presents a new algorithm based on the distance matrix to solve the LC-MST problem. The studied cases show that the presented algorithm is efficient to solve the LC-MST problem in less time. Also, the presented algorithm can be modified to solve the DC-MST (Delay Constrained-Minimum Spanning Tree) problem presented by Lee and Atiquzzaman (2007) and the MRCT (Minimum Routing Cost Tree) problem presented by Cambos and Ricardo (2008), given as the applications of the presented algorithm.

Given a graph G and a bound d ? 2, the bounded-diameter minimum spanning tree problem seeks a spanning tree on G of minimum weight subject to the constraint that its diameter does not exceed d. This problem is NP-hard; several heuristics have been proposed to find near-optimal solutions to it in reasonable times. A decentralized learning automata-based algorithm creates spanning trees that honor the diameter constraint. The algorithm rewards a tree if it has the smallest weight found so far and penalizes it otherwise. As the algorithm proceeds, the choice probability of the tree converges to one; and the algorithm halts when this probability exceeds a predefined value. Experiments confirm the superiority of the algorithm over other heuristics in terms of both speed and solution quality.

We study invasion percolation on Aldous’ Poisson-weighted infinite tree, and derive two distinct Markovian representations of the resulting process. One of these is the $\sigma \to \infty$ limit of a representation discovered by Angel et al. [Ann. Appl. Probab. 36 (2008) 420–466]. We also introduce an exploration process of a randomly weighted Poisson incipient infinite cluster. The dynamics of the new process are much more straightforward to describe than those of invasion percolation, but it turns out that the two processes have extremely similar behavior. Finally, we introduce two new ``stationary'' representations of the Poisson incipient infinite cluster as random graphs on $\mathbb{Z}$ which are, in particular, factors of a homogeneous Poisson point process on the upper half-plane $\mathbb{R} \times [0,\infty)$.

Given an undirected, vertex-weighted graph, the goal of the minimum weight vertex cover problem is to find a subset of the vertices of the graph such that the subset is a vertex cover and the sum of the weights of its vertices is minimal. This problem is known to be NP-hard and no efficient algorithm is known to solve it to optimality. Therefore, most existing techniques are based on heuristics for providing approximate solutions in a reasonable computation time. Population-based search approaches have shown to be effective for solving a multitude of combinatorial optimization problems. Their advantage can be identified as their ability to find areas of the space containing high quality solutions. This paper proposes a simple and efficient population-based iterated greedy algorithm for tackling the minimum weight vertex cover problem. At each iteration, a population of solutions is established and refined using a fast randomized iterated greedy heuristic based on successive phases of destruction and reconstruction. An extensive experimental evaluation on a commonly used set of benchmark instances shows that our algorithm outperforms current state-of-the-art approaches.

The degree-constrained minimum spanning tree (DCMST) problem is the problem of finding the minimum cost spanning tree in an edge weighted complete graph such that each vertex in the spanning tree has degree ≤ d for some d ≥ 2. The DCMST problem is known to be NP-hard. This paper presents an ant-based algorithm to find low cost degree-constrained spanning trees (DCST). The algorithm employs a set of ants which traverse the graph and identify a set of candidate edges, from which a DCST is constructed. Local optimization algorithms are then used to further improve the DCST. Extensive experiments using 612 problem instances show many improvements over existing algorithms.

The minimum cost-tree cover problem is to compute a minimum cost-tree T in a given connected graph G with costs on the edges, such that the vertices spanned by T form a vertex cover for G . The problem is supposed to occur in applications of vertex cover and in edge-dominating sets when additional connectivity is required for solutions. Whereas a linear-time 2 -approximation algorithm for the unweighted case has been known for quite a while, the best approximation ratio known for the weighted case is 3 . Moreover, the 3 -approximation algorithms for such cases are far from practical due to their inefficiency. In this article we present a fast, purely combinatorial 2 -approximation algorithm for the minimum cost-tree cover problem. It constructs a good approximate solution by trimming some leaves within a minimum spanning tree (MST); and, to determine which leaves to trim, it uses both the primal-dual schema and an instance layering technique adapted from the local ratio method.

This paper studies the sum-of-ratios version of the classical minimum spanning tree problem. We describe a branch-and-bound algorithm for solving the general version of the problem based on its image space representation. The suggested approach specifically addresses the difficulties arising in the case when the number of ratios exceeds two. The efficacy of our approach is demonstrated on randomly generated complete and sparse graph instances.

Minimum routing cost spanning tree - MRCT is one of spanning tree optimization problems having many applications in network design. In general cases, the problem is proved as NP-hard. This paper is going to propose 2 heuristic-based algorithms used for MRCT. The general idea of those algorithms is to start at a spanning tree and step by step improve edges to obtain better spanning tree. We conducted experiment implemetations for these proposals and obtained better result than the result of current approximate algorithms.

A spanning tree of a connected graph is a sub graph, with least number of edges that still spans. The problem of finding degree constraint spanning tree is known to be NP-hard. In this paper we discuss an Ant-Based algorithm for finding minimum degree spanning trees and give improvement of the algorithm. We also show comparisons among the three algorithms and find the best improved Ant-Based algorithm. Extensive experimental results show that our improved algorithm performs very well against other algorithms on a set of 50 problem instances. Keywords - Ant algorithm, Graph algorithms, Heuristic methods, minimum degree spanning tree, I. INTRODUCTION This paper describes Ant-Based algorithms for minimum degree spanning tree (AB-MDST) of unweighted connected graph. This is an interesting, real-world problem that seems well suited to an ant algorithm approach. The AB-MDST problem entails finding a spanning tree such that the maximum degree of a vertex in the tree becomes minimum (2). This concept is useful in the design of telecommunication networks, design of networks for computer communication, design of integrated circuits, energy networks, transportation, logistics, and sewage networks (3). For instance, switches in an actual communication network will have limited number of connections available. Transportation systems must place a limit on the number of roads meeting in one place. The problem of finding degree constraint spanning tree is NP-hard (9). Therefore, heuristics are often used to find good solutions in a reasonable amount of time (10). We have used one type of heuristic called Ant Colony Optimization (ACO) (10). Here, artificial ants move based on local information and pheromone levels. Our algorithm uses cumulative pheromone levels to determine candidate set of edges from which minimum degree spanning trees are built (7). In this paper, we compare 3 algorithms - AB-MDST without local search and without degree constraint, AB-MDST with local search but without degree constraint and the last one AB- MDST with local search and with degree constraint. Extensive experimental results show that AB-MDST with local search and with degree constraint performs very well against other algorithms. The rest of the paper is organized as follow. In section 2 Our Ant-Based algorithm and two improved versions of that algorithm are described. Section 3 compares the performances of the three algorithms. The conclusion is given in section 4.

The minimum spanning tree problem is a classical and well-known combinatorial optimization problem. There exist many efficient algorithms such as the Kruskal algorithm and Prim algorithm to solve it. But in a real network, the vertices as well as the edges may have weights, and there are many cases of the vertex weights according to the degrees of the vertices. In this paper, we consider the computational complexity of the minimum expense spanning tree problem, which is to find a spanning tree in a network with minimum total expenses. We show that this problem is NP-hard in some general situations. And we propose a polynomial time algorithm when computing all the weights of the vertices in a spanning tree.

Given edge weighted graph G(V, E) (all weights are nonnegative) where vertices can represent terminals, cities, etc., and edges can represent cables, road, etc., the Multi Period Degree Constrained Minimum Spanning Tree Problem (MPDCMST) is a problem of finding the total minimum installation cost whilst also maintaining the maximum number of edges incidence to every vertex. The restriction of the links on every vertex occurs to keep the reliability of the network. Moreover, the installation process also divided into some periods due to fund limitation. In this research we will discuss the hybrid between the depth first search technique and Kruskal's Algorithm applying to solve the MPDCMST problem.

Improving the lifetime of wireless sensor networks (WSNs) remains an open and active research area. One of the challenging problems in this field is the partitioning of a WSN into disjoint clusters so that the network lifetime is maximized. In particular, the selection of a head for each cluster should consider various parameters related to transmission costs. In this paper, we propose a novel clustering scheme based on hierarchical agglomerative clustering algorithm. The selection of the cluster heads is based on the proximity with a virtual node representing the optimal head location with respect to energy consumption. The proposed algorithm is re-executed at each packet delivering round to maintain energy efficiency during the whole network lifetime. In the transmission of packets to BS, we consider two cases: - Single Hop transmission between CHs and BS that, each CH directly send packets to BS. and - Multi-Hop transmission between the BS and CHs that, each CH transmits to another CH or to a base station according to the results obtained by the algorithm of the spanning tree Experimental results show that our clustering scheme is less energy-consuming than LEACH, HEED and clustering protocol using k-means algorithm.

Due to the hardness of solving the minimum spanning tree (MST) problem in stochastic environments, the stochastic MST (SMST) problem has not received the attention it merits, specifically when the probability distribution function (PDF) of the edge weight is not a priori known. In this paper, we first propose a learning automata-based sampling algorithm (Algorithm 1) to solve the MST problem in stochastic graphs where the PDF of the edge weight is assumed to be unknown. At each stage of the proposed algorithm, a set of learning automata is randomly activated and determines the graph edges that must be sampled in that stage. As the proposed algorithm proceeds, the sampling process focuses on the spanning tree with the minimum expected weight. Therefore, the proposed sampling method is capable of decreasing the rate of unnecessary samplings and shortening the time required for finding the SMST. The convergence of this algorithm is theoretically proved and it is shown that by a proper choice of the learning rate the spanning tree with the minimum expected weight can be found with a probability close enough to unity. Numerical results show that Algorithm 1 outperforms the standard sampling method. Selecting a proper learning rate is the most challenging issue in learning automata theory by which a good trade off can be achieved between the cost and efficiency of algorithm. To improve the efficiency (i.e., the convergence speed and convergence rate) of Algorithm 1, we also propose four methods to adjust the learning rate in Algorithm 1 and the resultant algorithms are called as Algorithm 2 through Algorithm 5. In these algorithms, the probabilistic distribution parameters of the edge weight are taken into consideration for adjusting the learning rate. Simulation experiments show the superiority of Algorithm 5 over the others. To show the efficiency of Algorithm 5, its results are compared with those of the multiple edge sensitivity method (MESM). The obtained results show that Algorithm 5 performs better than MESM both in terms of the running time and sampling rate.