Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 140 for “"Minimum spanning tree"”.
-
Computing a Diameter-constrained Minimum Spanning Tree
… it is necessary to find the smallest possible tree with a bounded diameter. A diameter-constrained minimum spanning tree (DCMST) of a given undirected, edge-weighted graph, G, is the smallest-weight spanning tree of all spanning trees of G which contain no path with more than k edges, where k …
-
Parallel Implementation of a Minimum Spanning Tree Algorithm
Building a Minimum Spanning Tree (MST) of a weighted undirected graph is an important step in various applications, including circuit design, and it is desirable to build the MST quickly. However, current well-known approaches for building MSTs are not highly parallel. In this thesis, I propose a …
-
On the shortest path and minimum spanning tree problems
The shortest path and minimum spanning tree problems are two of the classic textbook problems in combinatorial optimization. They are simple to describe and admit simple polynomial-time algorithms. However, despite years of concerted research effort, the asymptotic complexity of these problems …
-
Distributed broadcast and minimum spanning tree algorithms with low communication complexity
… we consider the problems of broadcast and minimum spanning tree construction in a distributed setting. These problems are of fundamental importance. Efficient solutions for these problems can lead to improvements in algorithms for a number of other distributed problems such as leader …
-
A contrasting look at network formation models and their application to the minimum spanning tree
… on problems related to the formation of minimum spanning trees and consider the cost of selfish behavior, more commonly known as the price of anarchy, in network formation. We also explore differences between local, decentralized methods for network formation and their global, centralized …
-
Combinatorial optimization and the analysis of randomized search heuristics
… optimization problems such as the minimum spanning tree problem or the problem of computing an Eulerian cycle of a given Eulerian graph and prove bounds on the runtime of simple evolutionary algorithms. For the minimum spanning tree problem we also investigate a multi-objective …
-
Algoritmos experimentais para o problema biobjetivo da árvore geradora quadrática em adjacência de arestas
The Quadratic Minimum Spanning Tree (QMST) problem is a generalization of the Minimum Spanning Tree problem in which, beyond linear costs associated to each edge, quadratic costs associated to each pair of edges must be considered. The quadratic costs are due to interaction costs between the edges. …
-
Γεωμετρικά γραφήματα με y-μονότονα και xy-μονότονα μονοπάτια: κατασκευή και αναγνώριση
… by a y−monotone path. The k−rooted y−monotone minimum spanning graph of a k−rooted point set P is the k−rooted y−monotone spanning graph of P that has the minimum cost. The cost of a geometric graph is the sum of the lengths of its edges. We deal with the problem of obtaining the rooted …
-
MULTIOBJECTIVE OPTIMIZATION MODELS AND SOLUTION METHODS FOR PLANNING LAND DEVELOPMENT USING MINIMUM SPANNING TREES, LAGRANGIAN RELAXATION AND DECOMPOSITION TECHNIQUES
… of compactness that involves the use of the minimum spanning tree is embedded into a mixed integer programming formulation. Despite the exponential number of variables and constraints required to define the minimum spanning tree, this problem was solved using a hybrid algorithm developed in …
-
Distributed construction of resource-efficient overlay tree by approximating MST
… Multicast Overlay) for constructing overlay tree to support video streaming applications. RESMO reduces network resource usage by approximating MST and achieves low end-to-end latency between the sender and each receiver at the same time. The resulting overlay is a compromise between minimum …
-
Robust and Survivable Network Design Considering Uncertain Node and Link Failures
… k=0, l=1, this problem becomes the well-known minimum spanning tree problem; and when k=0, l ≥ 1, this problem is to find a minimum-cost l-edge-connected spanning subgraph, while when k ≥ 2, l=0, the problem is to find a minimum-cost k-vertex-connected spanning subgraph. As a generalization of …
-
Graph Theory for the Secondary School Classroom.
… units in Graph Theory, namely Vertex Coloring, Minimum Spanning Tree, Domination, and Hamiltonian Paths and Cycles, which are appropriate for high school level.
-
O problema biobjetivo da árvore geradora quadrática em adjacência de arestas
The Quadratic Minimum Spanning Tree Problem (QMST) is a version of the Minimum Spanning Tree Problem in which, besides the traditional linear costs, there is a quadratic structure of costs. This quadratic structure models interaction effects between pairs of edges. Linear and quadratic costs are …
-
The Steiner Ratio for the Obstacle-Avoiding Steiner Tree Problem
This thesis examines the (geometric) Steiner tree problem: Given a set of points P in the plane, find a shortest tree interconnecting all points in P, with the possibility of adding points outside P, called the Steiner points, as additional vertices of the tree. The Steiner tree problem has been …
-
Situational Assessment using graph comparison
… similarities of the graphs using the concept of minimum spanning tree. The minimum spanning tree of a graph is a rough estimate of the details of the nodes and the edges of the graph. We therefore propose a new way of assessing a situation and a new way of analyzing the differences between the …
-
Αλγόριθμοι σχεδίασης δικτύων τοπολογίας δέντρου με ποικίλους περιορισμούς χωρητικότητας
… centralized networks often involves finding minimum cost spanning trees. One of the well-known problems that have been examined extensively in the literature is the Capacitated Minimum Spanning Tree (CMST) problem. In the CMST problem we are given a set of terminal nodes producing constant …
-
Design and implementation of a toolbox of modularized C programs to construct, analyze and test network optimization algorithms
… includes algorithms for graph coloring, minimum spanning tree and shortest path problems and some tools to analyze the results.
Page 1 of 7