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 167 for “"spanning trees"”.
-
Enumerating spanning trees
… and widely used theorem that there are n° - 2 trees on n labeled vertices [6, p. 70]. Since he originally stated it, the theorem has received much attention: people have proved it in many different ways. In this paper we consider three of these proofs. The first is an algebraic . result using …
-
Generating spanning trees
Algorithms for generating all spanning trees of a graph are presented. A series of improvements to the basic contraction-deletion algorithm results in the development of an algorithm which generates spanning trees in a Gray code order in constant amortized time. The improvements consist of removing …
-
Spanning Trails and Spanning Trees
… major parts in my dissertation. One is based on spanning trail, the other one is comparing spanning tree packing and covering.;The results of the spanning trail in my dissertation are motivated by Thomassen's Conjecture that every 4-connected line graph is hamiltonian. Harary and Nash-Williams …
-
Minimal spanning trees with degree restraints
… to the problem of determining the minimal spanning tree with degree restraints for a given non-directional graph. Section 1 gives an introduction to the problem. A set of definitions describing the graphical terminology used in the body of the thesis, is presented along with a description …
-
Connectivity and spanning trees of graphs
… edge connectivity and edge-disjoint spanning trees in graphs and hypergraphs from the following aspects.;1. Eigenvalue aspect. Let lambda2(G) and tau( G) denote the second largest eigenvalue and the maximum number of edge-disjoint spanning trees of a graph G, respectively. Motivated …
-
Counting Spanning Trees On Fractal Graphs
… Theorem, a closed form solution to the number of spanning trees on approximating graphs to a fully symmetric self-similar structure on ´ a finitely ramified fractal is given. Examples calculated include the Sierpinski ´ Gasket, a non-p.c.f. analog of the Sierpinski Gasket, the Diamond fractal, and …
-
Cycles, Disjoint Spanning Trees and Orientations of Graphs
… a simple realization G which has k-edge-disjoint spanning trees if and only if either both n = 1 and d1 = 0, or n ≥ 2 and both dn ≥ k and i=1n di ≥ 2k(n -- 1).;We investigate the emergence of specialized groups in a swarm of robots, using a simplified version of the stick-pulling problem [56], …
-
On graphs with large numbers of spanning trees
Thesis (Ph. D.)--Michigan State University. Department of Computer Science, 2005
-
Distributed program reliability based on minimum file spanning trees
… using Petri Nets based on Minimum File Sparming trees and to generate reliability measures for a distributed program in the given distributed computing environment. A global repair state was also incorporated into the final model to measure the availability of the program. (The idea proposed …
-
Optimal Bichromatic Plane Spanning Trees For Special Point Sets
… points, we desire to find T*, a minimum weight spanning tree such that every edge has one red endpoint and one blue endpoint and no two edges cross. We call T* a bichromatic plane minimum spanning tree (MinBPST). We say a point set is semi-collinear when the blue points lie on a line and the red …
-
Parallel computation of constrained spanning trees : heuristics and simd implementations
Doctor of Philosophy (Ph.D.)
-
Labeled Trees and Spanning Trees: Computational Discrete Mathematics and Applications
… exactly from 1 to n choose 2. Only five Leech trees are known and some non-existence results have been presented through the years. Variations of Leech trees such as the minimal distinct distance trees and modular Leech trees have been considered in recent years. In this thesis, such Leech-type …
-
Analysis of Algorithms for Finding All Spanning Trees of a Graph
Made available in DSpace on 2014-12-10T20:13:26Z (GMT). No. of bitstreams: 1 7114697.pdf: 2464146 bytes, checksum: 68120445ae87a9d8e5b5bd8ef7521b26 (MD5) Previous issue date: 1970
-
Bi-incidence Matrices of Graphs for Spanning Trees and Cycle Spaces
… bi-incidence matrix construction associated with spanning trees and cycle spaces. For a connected plane graph, let \(B\) be a reduced primal incidence matrix and let \(C\) be the reduced incidence matrix of the directed plane dual. Recent work proved that \(|\det([B\mid C])|=\tau(G)\), where …
-
Optimization of Contemporary Telecommunications Networks: Generalized Spanning Trees and WDM Optical Networks
… - the prize-collecting generalized minimum spanning tree problem (PCGMST) and the design of optical networks with wavelength division multiplexing. The first problem, the PCGMST problem, involves the design of regional backbone networks, where a set of local area networks (LANs) need to be …
-
Using Hyper-Dimensional Spanning Trees to Improve Structure Preservation During Dimensionality Reduction
… methods through the use of hyper-dimensional spanning trees to preserve complex clustering relationships in the original data. We demonstrate the approach with an interactive program for our dimension reduction algorithm, which allows the user to fine-tune the outcome.
Page 1 of 9