To see the other types of publications on this topic, follow the link: Trees (graph theory).
Dissertations / Theses on the topic 'Trees (graph theory)'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Trees (graph theory).'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Dawson, Shelly Jean. "Minimal congestion trees." CSUSB ScholarWorks, 2006. https://scholarworks.lib.csusb.edu/etd-project/3005.
Full textAbstract:
Analyzes the results of M.I. Ostrovskii's theorem of inequalities which estimate the minimal edge congestion for finite simple graphs. Uses the generic results of the theorem to examine and further reduce the parameters of inequalities for specific families of graphs, particularly complete graphs and complete bipartite graphs. Also, explores a possible minimal congestion tree for some grids while forming a conjecture for all grids.
2
Tang, Yin Ping Wendy. "Bandwidth of some classes of full directed trees." HKBU Institutional Repository, 1998. http://repository.hkbu.edu.hk/etd_ra/256.
Full text
3
Montgomery, Richard Harford. "Minors and spanning trees in graphs." Thesis, University of Cambridge, 2015. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.709278.
Full text
4
Mahoney, James Raymond. "Tree Graphs and Orthogonal Spanning Tree Decompositions." PDXScholar, 2016. http://pdxscholar.library.pdx.edu/open_access_etds/2944.
Full textAbstract:
Given a graph G, we construct T(G), called the tree graph of G. The vertices of T(G) are the spanning trees of G, with edges between vertices when their respective spanning trees differ only by a single edge. In this paper we detail many new results concerning tree graphs, involving topics such as clique decomposition, planarity, and automorphism groups. We also investigate and present a number of new results on orthogonal tree decompositions of complete graphs.
5
Humphries, Peter John. "Combinatorial Aspects of Leaf-Labelled Trees." Thesis, University of Canterbury. Mathematics and Statistics, 2008. http://hdl.handle.net/10092/1801.
Full textAbstract:
Leaf-labelled trees are used commonly in computational biology and in other disciplines, to depict the ancestral relationships and present-day similarities between both extant and extinct species. Studying these trees from a mathematical perspective provides a foundation for developing tools and techniques that have practical applications.
We begin by examining some quartet problems, namely determining the number of quartets that are required to infer the structure of a particular supertree. The quartet graph is introduced as a tool for tackling quartet problems, and is subsequently used to give new characterisations of compatible, definitive and identifying quartet sets.
We then turn to investigating some properties of the subtrees induced by a
collection of trees. This is motivated in part by the problem of reconstructing
two or more trees simultaneously from their combined collection of subtrees.
We also use some ideas drawn from Ramsey theory to show the existence of
arbitrarily large common subtrees.
Finally, we explore some extremal properties of the metric that is induced
by the tree bisection and reconnection operation. This includes finding new
(asymptotically) tight upper and lower bounds on both the size of the neighbourhoods in the metric space and on the diameter of the corresponding
adjacency graph.
6
Zhang, Xinyi. "Expected lengths of minimum spanning trees." Access to citation, abstract and download form provided by ProQuest Information and Learning Company; downloadable PDF file, 139 p, 2008. http://proquest.umi.com/pqdweb?did=1597617641&sid=6&Fmt=2&clientId=8331&RQT=309&VName=PQD.
Full text
7
Tam, Wing Ka. "The strong chromatic index of cubic Halin graphs." HKBU Institutional Repository, 2003. http://repository.hkbu.edu.hk/etd_ra/516.
Full text
8
Jayasooriya, Arachchilage Dinush Lanka Panditharathna. "Spanning Trees of Certain Types." OpenSIUC, 2016. https://opensiuc.lib.siu.edu/theses/2049.
Full textAbstract:
A Spanning tree of a graph G is a subgraph that is a tree which concludes all of the vertices of G. And a graph G is bipartite if the vertex set of G can be partitioned in to two sets A and B, such that every edge of G joins a vertex of A and a vertex of B. We can see that every tree(including spanning tree) is bipartite. We define type of a spanning tree using this idea as follows: We divide vertices of a spanning trees in to two partitions A and B by using its bipartition. Then, we define type of the spanning tree by (| A |, | B |), provided | A | less than or equal to | B |. We first identify the characteristics for a graph to have a spanning trees of a certain type. Then, implement some theorems about the type.
9
Curran, Sean P. "Independent trees in 4-connected graphs." Diss., Georgia Institute of Technology, 2003. http://hdl.handle.net/1853/29842.
Full text
10
Janzen, David. "The smallest irreducible lattices in the product of trees /." Thesis, McGill University, 2007. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=101884.
Full textAbstract:
We produce a nonpositively curved square complex, X, containing exactly four squares. Its universal cover, X̃ ≅ T4 x T 4, is isomorphic to the product of two 4-valent trees. The group, pi1X, is a lattice in Aut (X̃) but π1X is not virtually a nontrivial product of free groups. There is no such example with fewer than four squares. The main ingredient in our analysis is that X̃ contains an "anti-torus" which is a certain aperiodically tiled plane.
11
King, Andrew James Howell. "On decomposition of complete infinite graphs into spanning trees." Thesis, University of Reading, 1990. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.253454.
Full text
12
Broutin, Nicolas. "Shedding new light on random trees." Thesis, McGill University, 2007. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=102963.
Full textAbstract:
We introduce a weighted model of random trees and analyze the asymptotic properties of their heights. Our framework encompasses most trees of logarithmic height that were introduced in the context of the analysis of algorithms or combinatorics. This allows us to state a sort of "master theorem" for the height of random trees, that covers binary search trees (Devroye, 1986), random recursive trees (Devroye, 1987; Pittel, 1994), digital search trees (Pittel, 1985), scale-free trees (Pittel, 1994; Barabasi and Albert, 1999), and all polynomial families of increasing trees (Bergeron et al., 1992; Broutin et al., 2006) among others. Other applications include the shape of skinny cells in geometric structures like k-d and relaxed k-d trees.<br>This new approach sheds new light on the tight relationship between data structures like trees and tries that used to be studied separately. In particular, we show that digital search trees and the tries built from sequences generated by the same memoryless source share the same stable core. This link between digital search trees and tries is at the heart of our analysis of heights of tries. It permits us to derive the height of several species of tries such as the trees introduced by de la Briandais (1959) and the ternary search trees of Bentley and Sedgewick (1997).<br>The proofs are based on the theory of large deviations. The first order terms of the asymptotic expansions of the heights are geometrically characterized using the Crame'r functions appearing in estimates of the tail probabilities for sums of independent random variables.
13
Chan, Wai Hong. "Bandwidth problems of graphs." HKBU Institutional Repository, 1996. http://repository.hkbu.edu.hk/etd_ra/62.
Full text
14
Reiter, Richard M. "Prediction of recurrence in thin melanoma using trees and random forests /." Electronic version (PDF), 2005. http://dl.uncw.edu/etd/2005/reiterr/richardreiter.html.
Full text
15
Okoth, Isaac Owino. "Combinatorics of oriented trees and tree-like structures." Thesis, Stellenbosch : Stellenbosch University, 2015. http://hdl.handle.net/10019.1/96860.
Full textAbstract:
Thesis (PhD)--Stellenbosch University, 2015.<br>ENGLISH ABSTRACT : In this thesis, a number of combinatorial objects are enumerated. Du and
Yin as well as Shin and Zeng (by a different approach) proved an elegant
formula for the number of labelled trees with respect to a given in degree
sequence, where each edge is oriented from a vertex of lower label towards
a vertex of higher label. We refine their result to also take the number of
sources (vertices of in degree 0) or sinks (vertices of out degree 0) into account.
We find formulas for the mean and variance of the number of sinks
or sources in these trees. We also obtain a differential equation and a functional
equation satisfied by the generating function for these trees. Analogous
results for labelled trees with two marked vertices, related to functional
digraphs, are also established.
We extend the work to count reachable vertices, sinks and leaf sinks in
these trees. Among other results, we obtain a counting formula for the number
of labelled trees on n vertices in which exactly k vertices are reachable
from a given vertex v and also the average number of vertices that are reachable
from a specified vertex in labelled trees of order n.
In this dissertation, we also enumerate certain families of set partitions
and related tree-like structures. We provide a proof for a formula that counts
connected cycle-free families of k set partitions of {1, . . . , n} satisfying a certain
coherence condition and then establish a bijection between these families and the set of labelled free k-ary cacti with a given vertex-degree distribution.
We then show that the formula also counts coloured Husimi graphs
in which there are no blocks of the same colour that are incident to one another.
We extend the work to count coloured oriented cacti and coloured
cacti.
Noncrossing trees and related tree-like structures are also considered in
this thesis. Specifically, we establish formulas for locally oriented noncrossing
trees with a given number of sources and sinks, and also with given
indegree and outdegree sequences. The work is extended to obtain the average
number of reachable vertices in these trees. We then generalise the
concept of noncrossing trees to find formulas for the number of noncrossing
Husimi graphs, cacti and oriented cacti. The study is further extended
to find formulas for the number of bicoloured noncrossing Husimi graphs
and the number of noncrossing connected cycle-free pairs of set partitions.<br>AFRIKAANSE OPSOMMING : In hierdie tesis word ’n aantal kombinatoriese objekte geenumereer. Du
en Yin asook Shin en Zeng (deur middel van ’n ander benadering) het ’n
elegante formule vir die aantal geëtiketteerde bome met betrekking tot ’n
gegewe ingangsgraadry, waar elke lyn van die nodus met die kleiner etiket
na die nodus met die groter etiket toe georiënteer word. Ons verfyn hul
resultaat deur ook die aantal bronne (nodusse met ingangsgraad 0) en putte
(nodusse met uitgangsgraad 0) in ag te neem. Ons vind formules vir die gemiddelde
en variansie van die aantal putte of bronne in hierdie bome. Ons
bepaal verder ’n differensiaalvergelyking en ’n funksionaalvergelyking wat
deur die voortbringende funksie van hierdie bome bevredig word. Analoë
resultate vir geëtiketteerde bome met twee gemerkte nodusse (wat verwant
is aan funksionele digrafieke), is ook gevind.
Ons gaan verder voort deur ook bereikbare nodusse, bronne en putte in
hierdie bome at te tel. Onder andere verkry ons ’n formule vir die aantal geëtiketteerde
bome met n nodusse waarin presies k nodusse vanaf ’n gegewe
nodus v bereikbaar is asook die gemiddelde aantal nodusse wat bereikbaar
is vanaf ’n gegewe nodus.
Ons enumereer in hierdie tesis verder sekere families van versamelingsverdelings
en soortgelyke boom-vormige strukture. Ons gee ’n bewys vir ’n
formule wat die aantal van samehangende siklus-vrye families van k versamelingsverdelings
op {1, . . . , n} wat ’n sekere koherensie-vereiste bevredig,
en ons beskryf ’n bijeksie tussen hierdie familie en die versameling van
geëtiketteerde vrye k-êre kaktusse met ’n gegewe nodus-graad-verdeling.
Ons toon ook dat hierdie formule ook gekleurde Husimi-grafieke tel waar
blokke van dieselfde kleur nie insident met mekaar mag wees nie. Ons tel
verder ook gekleurde georiënteerde kaktusse en gekleurde kaktusse.
Nie-kruisende bome en soortgelyke boom-vormige strukture word in
hierdie tesis ook beskou. On bepaal spesifiek formules vir lokaal georiënteerde
nie-kruisende bome wat ’n gegewe aantal bronne en putte het asook
nie-kruisende bome met gegewe ingangs- en uitgangsgraadrye. Ons
gaan voort deur die gemiddelde aantal bereikbare nodusse in hierdie bome
te bepaal. Ons veralgemeen dan die konsep van nie-kruisende bome en
vind formules vir die aantal nie-kruisende Husimi-grafieke, kaktusse en
georiënteerde kaktusse. Laastens vind ons ’n formule vir die aantaal tweegekleurde
nie-kruisende Husimi-grafieke en die aantal nie-kruisende samehangende
siklus-vrye pare van versamelingsverdelings.
16
Lauer, Joseph. "Cubulating one-relator groups with torsion." Thesis, McGill University, 2007. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=101861.
Full textAbstract:
Let <a1,..., a m | wn> be a presentation of a group G, where w is freely and cyclically reduced and n ≥ 2 is maximal. We define a system of codimension-1 subspaces in the universal cover, and invoke a construction essentially due to Sageev to define an action of G on a CAT(0) cube complex. By proving easily formulated geometric properties of the codimension-1 subspaces we show that when n ≥ 4 the action is proper and cocompact, and that the cube complex is finite dimensional and locally finite. We also prove partial results when n = 2 or n = 3. It is also shown that the subgroups of G generated by non-empty proper subsets of {a1, a 2,..., am} embed by isometries into the whole group.
17
Lee, William W. L. (William Wai Lam) Carleton University Dissertation Computer Science. "Tree editing algorithms." Ottawa, 1992.
Find full text
18
Przytycka, Teresa Maria. "Parallel techniques for construction of trees and related problems." Thesis, University of British Columbia, 1990. http://hdl.handle.net/2429/30640.
Full textAbstract:
The concept of a tree has been used in various areas of mathematics for over a century. In particular, trees appear to be one of the most fundamental notions in computer science. Sequential algorithms for trees are generally well studied. Unfortunately many of these sequential algorithms use methods which seem to be inherently sequential. One of the contributions of this thesis is the introduction of several parallel techniques for the construction of various types of trees and the presentation of new parallel tree construction algorithms using these methods. Along with the parallel tree construction techniques presented here, we develop techniques which have broader applications.
We use the Parallel Random Access Machine as our model of computation. We consider two basic methods of constructing trees:tree expansion and tree synthesis.
In the tree expansion method, we start with a single vertex and construct a tree by adding nodes of degree one and/or by subdividing edges. We use the parallel tree expansion technique to construct the tree representation for graphs in the family of graphs known as cographs.
In the tree synthesis method, we start with a forest of single node subtrees and construct a tree by adding edges or (for rooted trees) by creating parent nodes for some roots of the trees in the forest. We present a family of parallel and sequential algorithms to construct various approximations to the Huffman tree. All these algorithms apply the tree synthesis method by constructing a tree in a level-by-level fashion. To support one of the algorithms in the family we develop a technique which we call the cascading sampling technique.
One might suspect that the parallel tree synthesis method can be applied only to trees of polylogarithmic height, but this is not the case.We present a technique which we call the valley filling technique and develop its accelerated version called the accelerated valley filling technique. We present an application of this technique to an optimal parallel algorithm for construction of minimax trees.<br>Science, Faculty of<br>Computer Science, Department of<br>Graduate
19
Walvoort, Clayton A. "Peg Solitaire on Trees with Diameter Four." Digital Commons @ East Tennessee State University, 2013. https://dc.etsu.edu/etd/1113.
Full textAbstract:
In a paper by Beeler and Hoilman, the traditional game of peg solitaire is generalized to graphs in the combinatorial sense. One of the important open problems in this paper was to classify solvable trees. In this thesis, we will give necessary and sufficient conditions for the solvability for all trees with diameter four. We also give the maximum number of pegs that can be left on such a graph under the restriction that we jump whenever possible.
20
Zhang, Yuanping. "Counting the number of spanning trees in some special graphs /." View Abstract or Full-Text, 2002. http://library.ust.hk/cgi/db/thesis.pl?COMP%202002%20ZHANG.
Full text
21
Jonsson, Jakob. "Simplicial complexes of graphs /." Berlin [u.a.] : Springer, 2008. http://dx.doi.org/10.1007/978-3-540-75858-7.
Full text
22
Ho, Yiu Yu. "Global secure sets of trees and grid-like graphs." Doctoral diss., University of Central Florida, 2011. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/4922.
Full textAbstract:
However, as will be demonstrated in Chapter 1, a defensive alliance may not be able to properly defend itself when multiple members are under attack at the same time. The concept of secure sets is introduced in (BDH07) for exactly this purpose. The non-empty set S is a secure set if every subset Xsubset of]S, with the assistance of vertices in S, can successfully defend against simultaneous attacks coming from vertices outside of S. The exact definition of simultaneous attacks and how such attacks may be defended will be provided in Chapter 1. In (BDH07), the authors presented an interesting characterization for secure sets which resembles the definition of defensive alliances. A non-empty set S is a secure set if and only if for all] X subset of] S, vertical line]N (X) intersection] Svertical line] greater than or equal to] vertical line]N(X) - Svertical line] ((BDH07),Theorem 11). The cardinality of a minimum secure set is the security number of G, denoted s(G). A secure set S is a global secure set if it further satisfies N (S)= V. The cardinality of a minimum global secure set of G is the global security number of G, denoted gamma subscript s](G). In this work, we present results on secure sets and global secure sets. In particular, we treat the computational complexity of finding the security number of a graph, present algorithms and bounds for the global security numbers of trees, and present the exact values of the global security numbers of paths, cycles and their Cartesian products.; Let G = (V, E) be a graph and let S subset of] V be a subset of vertices. The set S is a defensive alliance if for all x element of] S, vertical line]N(x)intersection] Svertical line]greater than or equal to] vertical line]N(x) - Svertical line]. The concept of defensive alliances was introduced in (KHH04), primarily for the modeling of nations in times of war, where allied nations are in mutual agreement to join forces if anyone of them is attacked. For a vertex x in a defensive alliance, the number of neighbors of x inside the alliance, plus the vertex x, is at least the number of neighbors of x outside the alliance. In a graph model, the vertices of a graph represent nations and the edges represent country boundaries. Thus, if the nation corresponding to a vertex x is attacked by its neighbors outside the alliance, the attack can be thwarted by x with the assistance of its neighbors in the alliance. In a different subject matter, (FLG00) applies graph theory to model the world wide web, where vertices represent websites and edges represent links between websites. A web community is a subset of vertices of the web graph, such that every vertex in the community has at least as many neighbors in the set as it has outside. So, a web community C satisfies for all] x element of] C, vertical line]N(x) intersection] Cvertical line] greater than] vertical line]N(x) - Cvertical line]. These sets are very similar to defensive alliances. They are known as strong defensive alliances in the literature of alliances in graphs. Other areas of application for alliances and related topics include classification, data clustering, ecology, business and social networks. Consider the application of modeling nations in times of war introduced in the first paragraph. In a defensive alliance, any attack on a single member of the alliance can be successfully defended.<br>ID: 030423421; System requirements: World Wide Web browser and PDF reader.; Mode of access: World Wide Web.; Thesis (Ph.D.)--University of Central Florida, 2011.; Includes bibliographical references (p. 206-210).<br>Ph.D.<br>Doctorate<br>Electrical Engineering and Computer Science<br>Engineering and Computer Science
23
Chen, Calvin Ching-Yuen. "Efficient Parallel Algorithms and Data Structures Related to Trees." Thesis, University of North Texas, 1991. https://digital.library.unt.edu/ark:/67531/metadc332626/.
Full textAbstract:
The main contribution of this dissertation proposes a new paradigm, called the parentheses matching paradigm. It claims that this paradigm is well suited for designing efficient parallel algorithms for a broad class of nonnumeric problems. To demonstrate its applicability, we present three cost-optimal parallel algorithms for breadth-first traversal of general trees, sorting a special class of integers, and coloring an interval graph with the minimum number of colors.
24
Haslegrave, John George Ernest. "Extremal results on hypergraphs, trees and regular graphs." Thesis, University of Cambridge, 2011. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.609876.
Full text
25
余鳳玲 and Fung-ling Yue. "On the complexity of finding optimal edge rankings." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 1996. http://hub.hku.hk/bib/B30148881.
Full text
26
王慧霞 and Wai-ha Wong. "Efficient algorithms for broadcast routing." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 1996. http://hub.hku.hk/bib/B31214733.
Full text
27
Yue, Fung-ling. "On the complexity of finding optimal edge rankings /." Hong Kong : University of Hong Kong, 1996. http://sunzi.lib.hku.hk/hkuto/record.jsp?B18540247.
Full text
28
Wong, Wai-ha. "Efficient algorithms for broadcast routing /." Hong Kong : University of Hong Kong, 1996. http://sunzi.lib.hku.hk/hkuto/record.jsp?B18565402.
Full text
29
Irniger, Christophe-André. "Graph matching filtering databases of graphs using machine learning techniques." Berlin Aka, 2005. http://deposit.ddb.de/cgi-bin/dokserv?id=2677754&prov=M&dok_var=1&dok_ext=htm.
Full text
30
Ibarra, Louis Walter. "Dynamic algorithms for chordal and interval graphs." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2001. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/NQ58573.pdf.
Full text
31
Razanajatovo, Misanantenaina Valisoa. "Properties of greedy trees." Thesis, Stellenbosch : Stellenbosch University, 2014. http://hdl.handle.net/10019.1/95909.
Full textAbstract:
Thesis (MSc)--Stellenbosch University, 2014.<br>ENGLISH ABSTRACT: A greedy tree is constructed from a given degree sequence using a simple
greedy algorithm that assigns the highest degree to the root, the second,
the third, . . . , -highest degree to the root’s neighbours, etc. This particular
tree is the solution to numerous extremal problems among all trees with
given degree sequence. In this thesis, we collect results for some distancebased
graph invariants, the number of subtrees and the spectral radius
in which greedy trees play a major role. We show that greedy trees are
extremal for the aforementioned graph invariants by means of two different
approaches, one using level greedy trees and majorization, while the other
one is somewhat more direct. Finally, we prove some new results on greedy
trees for additive parameters with specific toll functions.<br>AFRIKAANSE OPSOMMING: ’n Gulsige boom word vanuit ’n gegewe graadry deur middel van ’n eenvoudige
gulsige algoritme gebou, wat die hoogste graad aan die wortel
toewys, die tweede-, derde-, . . . , -hoogste graad aan die wortel se bure,
ens. Hierdie spesifieke boom is die oplossing van ’n groot aantal ekstremale
probleme onder al die bome met gegewe graadry. In hierdie tesis
beskou ons ’n versameling van resultate oor afstand-gebaseerde grafiekinvariante,
die aantal subbome en die spektraalstraal waarin gulsige bome
’n belangrike rol speel. Ons bewys dat gulsige bome ekstremaal vir die
bogenoemde grafiekinvariante is deur van twee verskillende tegnieke gebruik
te maak: een met behulp van vlak-gulsige bome en majorering, en
’n ander metode wat effens meer direk is. Laastens bewys ons sommige
nuwe resultate oor gulsige bome vir additiewe parameters met spesifieke
tolfunksies.
32
England, Alyssa. "Trees with Unique Italian Dominating Functions of Minimum Weight." Digital Commons @ East Tennessee State University, 2020. https://dc.etsu.edu/etd/3741.
Full textAbstract:
An Italian dominating function, abbreviated IDF, of $G$ is a function $f \colon V(G) \rightarrow \{0, 1, 2\}$ satisfying the condition that for every vertex $v \in V(G)$ with $f(v)=0$, we have $\sum_{u \in N(v)} f(u) \ge 2$. That is, either $v$ is adjacent to at least one vertex $u$ with $f(u) = 2$, or to at least two vertices $x$ and $y$ with $f(x) = f(y) = 1$. The Italian domination number, denoted $\gamma_I$(G), is the minimum weight of an IDF in $G$. In this thesis, we use operations that join two trees with a single edge in order to build trees with unique $\gamma_I$-functions.
33
Wang, Yinhua. "Fleet assignment, eulerian subtours and extended steiner trees." Diss., Georgia Institute of Technology, 1995. http://hdl.handle.net/1853/24922.
Full text
34
Abdalla, Ayman Mahmoud. "Computing a diameter-constrained minimum spanning tree." Doctoral diss., University of Central Florida, 2001. http://digital.library.ucf.edu/cdm/ref/collection/RTD/id/5567.
Full textAbstract:
University of Central Florida College of Engineering Thesis<br>In numerous practical applications, 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 is a given positive integer. The problem of finding a DCMST is NP-complete for all values of k; 4 <= k <= (n - 2), except when all edge-weights are identical. A DCMST is essential for the efficiency of various distributed mutual exclusion algorithms, where it can minimize the number of messages communicated among processors per critical section. It is also useful in linear lightwave networks, where it can minimize interference in the network by limiting the traffic in the network lines. Another practical application requiring a DCMST arises in data compression, where some algorithms compress a file utilizing a data-structure, and decompress a path in the tree to access a record A DCMST helps such algorithm to be fast without sacrificing a lot of storage storage space .<br>Ph.D.<br>School of Electrical Engineering and Computer Science<br>Engineering and Computer Science<br>Electrical Engineering and Computer Science<br>172 p.
35
Jung, Ho-Won. "Direct sparse matrix methods for interior point algorithms." Diss., The University of Arizona, 1990. http://hdl.handle.net/10150/185133.
Full textAbstract:
Recent advances in linear programming solution methodology have focused on interior point algorithms. These are powerful new methods, achieving significant reductions in computer time for large LPs and solving problems significantly larger than previously possible. This dissertation describes the implementation of interior point algorithms. It focuses on applications of direct sparse matrix methods to sparse symmetric positive definite systems of linear equations on scalar computers and vector supercomputers. The most computationally intensive step in each iteration of any interior point algorithm is the numerical factorization of a sparse symmetric positive definite matrix. In large problems or relatively dense problems, 80-90% or more of computational time is spent in this step. This study concentrates on solution methods for such linear systems. It is based on modifications and extensions of graph theory applied to sparse matrices. The row and column permutation of a sparse symmetric positive definite matrix dramatically affects the performance of solution algorithms. Various reordering methods are considered to find the best ordering for various numerical factorization methods and computer architectures. It is assumed that the reordering method will follow the fill-preserving rule, i.e., not allow additional fill-ins beyond that provided by the initial ordering. To follow this rule, a modular approach is used. In this approach, the matrix is first permuted by using any minimum degree heuristic, and then the permuted matrix is again reordered according to a specific reordering objective. Results of different reordering methods are described. There are several ways to compute the Cholesky factor of a symmetric positive definite matrix. A column Cholesky algorithm is a popular method for dense and sparse matrix factorization on serial and parallel computers. Applying this algorithm to a sparse matrix requires the use of sparse vector operations. Graph theory is applied to reduce sparse vector computations. A second and relatively new algorithm is the multifrontal algorithm. This method uses dense operations for sparse matrix computation at the expense of some data manipulation. The performance of the column Cholesky and multifrontal algorithms in the numerical factorization of a sparse symmetric positive definite matrix on an IBM 3090 vector supercomputer is described.
36
Wilson, Keith Eirik. "Factoring Semiprimes Using PG2N Prime Graph Multiagent Search." PDXScholar, 2011. https://pdxscholar.library.pdx.edu/open_access_etds/219.
Full textAbstract:
In this thesis a heuristic method for factoring semiprimes by multiagent depth-limited search of PG2N graphs is presented. An analysis of PG2N graph connectivity is used to generate heuristics for multiagent search. Further analysis is presented including the requirements on choosing prime numbers to generate 'hard' semiprimes; the lack of connectivity in PG1N graphs; the counts of spanning trees in PG2N graphs; the upper bound of a PG2N graph diameter and a conjecture on the frequency distribution of prime numbers on Hamming distance. We further demonstrated the feasibility of the HD2 breadth first search of PG2N graphs for factoring small semiprimes. We presented the performance of different multiagent search heuristics in PG2N graphs showing that the heuristic of most connected seedpick outperforms least connected or random connected seedpick heuristics on small PG2N graphs of size N
37
Lattanzi, Mark R. "Table-driven quadtree traversal algorithms." Thesis, Virginia Tech, 1989. http://hdl.handle.net/10919/44120.
Full textAbstract:
Two quadtree algorithms are presented that use table driven traversals to reduce the time complexity required to achieve their respective goals. The first algorithm is a two step process that converts a boundary representation of a polygon into a corresponding region representation of the same image. The first step orders the border pixels of the polygon.
The second step fills in the polygon in O(B) time where B is the number of border pixels for the polygon of interest. A table propagates the correct values of upcoming nodes in a simulated traversal of the final region quadtree. This is unique because the pointer representation of the tree being traversed does not exist. A linear quadtree representation is constructed as this traversal proceeds.
The second algorithm is an update algorithm for a quadtree (or octtree) of moving particles. Particle simulations have had the long-standing problem of calculating the interactions among n particles. It takes O(n2) time for direct computation of all the interactions between n particles. Greengard [Gree87, Carr87] has devised a way to approximate these calculations in linear time using a tree data structure. However, the particle simulation must still rebuild the particle tree after every iteration, which requires O(n log n) time. Our algorithm updates the existing tree of particles, rather than building a new tree.
It operates in near linear time in the number of particles being simulated. The update algorithm uses a table to store particles as they move between nodes of the tree.<br>Master of Science
38
Pavuluri, Manoj Kumar. "Fuzzy decision tree classification for high-resolution satellite imagery /." free to MU campus, to others for purchase, 2003. http://wwwlib.umi.com/cr/mo/fullcit?p1418056.
Full text
39
West, Raymond Troy Jr. "On the performance of B-trees using dynamic address computation." Thesis, Virginia Tech, 1985. http://hdl.handle.net/10919/41574.
Full textAbstract:
<p>The B-tree is a one of the more popular methods in use today for indexes and inverted files in database management
systems. The traditional implementation of a Bâ tree uses
many pointers (more than one per key), which can directly
affect the performance of the B-tree. A general method of
file organization and access (called Dymanic Address
Computation) has been described by Cook that can be used to
implement B-trees using no pointers. A minimal amount of storage (in addition to the keys) is required. An
implementation of Dynamic Address Computation and a B-tree
management package is described. Analytical performance
measures are derived in an attempt to understand the
performance characteristics of the B-tree. It is shown that
the additional costs associated with Dynamic Address
Computation result in an implementation that is competitive
with traditional implementations only for small
applications. For very large B-trees, additional work is required to make the performance acceptable. Some examples
of possible modifications are discussed.</p><br>Master of Science
40
Xuan, Mingzhi. "On Steinhaus Sets, Orbit Trees and Universal Properties of Various Subgroups in the Permutation Group of Natural Numbers." Thesis, University of North Texas, 2012. https://digital.library.unt.edu/ark:/67531/metadc149691/.
Full textAbstract:
In the first chapter, we define Steinhaus set as a set that meets every isometric copy of another set at exactly one point. We show that there is no Steinhaus set for any four-point subset in a plane.In the second chapter, we define the orbit tree of a permutation group of natural numbers, and further introduce compressed orbit trees. We show that any rooted finite tree can be realized as a compressed orbit tree of some permutation group. In the third chapter, we investigate certain classes of closed permutation groups of natural numbers with respect to their universal and surjectively universal groups. We characterize two-sided invariant groups, and prove that there is no universal group for countable groups, nor universal group for two-sided invariant groups in permutation groups of natural numbers.
41
Brooks, Jeffrey. "Edge-to-edge multicast overlay trees for real time video distribution /." free to MU campus, to others for purchase, 2003. http://wwwlib.umi.com/cr/mo/fullcit?p1418008.
Full text
42
Kwok, Wing-hong, and 郭永康. "Streamlined and prioritized hierarchical relations: a technique for improving the effectiveness of theclassification-tree methodology." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2001. http://hub.hku.hk/bib/B2975107X.
Full text
43
Bedrax-Weiss, Tania. "Optimal search protocols /." view abstract or download file of text, 1999. http://wwwlib.umi.com/cr/uoregon/fullcit?p9948016.
Full textAbstract:
Thesis (Ph. D.)--University of Oregon, 1999.<br>Typescript. Includes vita and abstract. Includes bibliographical references (leaves 206-211). Also available for download via the World Wide Web; free to University of Oregon users. Address: http://wwwlib.umi.com/cr/uoregon/fullcit?p9948016.
44
Bethlehem, Tobias. "Theory of 3-4 Heap." Thesis, University of Canterbury. Computer Science and Software Engineering, 2008. http://hdl.handle.net/10092/1930.
Full textAbstract:
As an alternative to the Fibonacci heap, and a variation of the 2-3 heap data structure by Tadao Takaoka, this research presents the 3-4 heap data structure. The aim is to prove that the 3-4 heap, like its counter-part 2-3 heap, also supports n insert, n delete-min, and m decrease-key operations, in O(m + nlog n) time. Many performance tests were carried out during this research comparing the 3-4 heap against the 2-3 heap and for a narrow set of circumstances the 3-4 heap outperformed the 2-3 heap.
The 2-3 heap has got a structure based on dimensions which are rigid using ternary linking and this path is made up of three nodes linked together to form a trunk, and the trunk is permitted to shrink by one. If further shrinkage is required then an adjustment is made by moving a few nodes from nearby positions to ensure the heaps rigid dimensions are retained. Should this no longer be the case, then the adjustment will trigger a make-up event, which propagates to higher dimensions, and requires amortised analysis. To aid amortised analysis, the trunk is given a measurement value called potential and this is the number of comparisons required to place each node into its correct position in ascending order using linear search.
The divergence of the 3-4 heap from the 2-3 heap is that the trunk maximum is increased by one to four and is still permitted to shrink by one. This modified data structure will have a wide range of applications as the data storage mechanism used by graph algorithms such as Dijkstra's 'Single Source Shortest Path'.
45
Lamont, Morné Michael Connell. "Binary classification trees : a comparison with popular classification methods in statistics using different software." Thesis, Stellenbosch : Stellenbosch University, 2002. http://hdl.handle.net/10019.1/52718.
Full textAbstract:
Thesis (MComm) -- Stellenbosch University, 2002.<br>ENGLISH ABSTRACT: Consider a data set with a categorical response variable and a set of explanatory
variables. The response variable can have two or more categories and the explanatory
variables can be numerical or categorical. This is a typical setup for a classification
analysis, where we want to model the response based on the explanatory variables.
Traditional statistical methods have been developed under certain assumptions
such as: the explanatory variables are numeric only and! or the data follow a multivariate
normal distribution. hl practice such assumptions are not always met. Different research
fields generate data that have a mixed structure (categorical and numeric) and researchers
are often interested using all these data in the analysis. hl recent years robust methods
such as classification trees have become the substitute for traditional statistical methods
when the above assumptions are violated. Classification trees are not only an effective
classification method, but offer many other advantages.
The aim of this thesis is to highlight the advantages of classification trees. hl the
chapters that follow, the theory of and further developments on classification trees are
discussed. This forms the foundation for the CART software which is discussed in
Chapter 5, as well as other software in which classification tree modeling is possible. We
will compare classification trees to parametric-, kernel- and k-nearest-neighbour
discriminant analyses. A neural network is also compared to classification trees and
finally we draw some conclusions on classification trees and its comparisons with other
methods.<br>AFRIKAANSE OPSOMMING: Beskou 'n datastel met 'n kategoriese respons veranderlike en 'n stel verklarende
veranderlikes. Die respons veranderlike kan twee of meer kategorieë hê en die
verklarende veranderlikes kan numeries of kategories wees. Hierdie is 'n tipiese opset vir
'n klassifikasie analise, waar ons die respons wil modelleer deur gebruik te maak van die
verklarende veranderlikes.
Tradisionele statistiese metodes is ontwikkelonder sekere aannames soos: die
verklarende veranderlikes is slegs numeries en! of dat die data 'n meerveranderlike
normaal verdeling het. In die praktyk word daar nie altyd voldoen aan hierdie aannames
nie. Verskillende navorsingsvelde genereer data wat 'n gemengde struktuur het
(kategories en numeries) en navorsers wil soms al hierdie data gebruik in die analise. In
die afgelope jare het robuuste metodes soos klassifikasie bome die alternatief geword vir
tradisionele statistiese metodes as daar nie aan bogenoemde aannames voldoen word nie.
Klassifikasie bome is nie net 'n effektiewe klassifikasie metode nie, maar bied baie meer
voordele.
Die doel van hierdie werkstuk is om die voordele van klassifikasie bome uit te
wys. In die hoofstukke wat volg word die teorie en verdere ontwikkelinge van
klassifikasie bome bespreek. Hierdie vorm die fondament vir die CART sagteware wat
bespreek word in Hoofstuk 5, asook ander sagteware waarin klassifikasie boom
modelering moontlik is. Ons sal klassifikasie bome vergelyk met parametriese-, "kernel"-
en "k-nearest-neighbour" diskriminant analise. 'n Neurale netwerk word ook vergelyk
met klassifikasie bome en ten slote word daar gevolgtrekkings gemaak oor klassifikasie
bome en hoe dit vergelyk met ander metodes.
46
Ocansey, Evans Doe. "Enumeration problems on lattices." Thesis, Stellenbosch : Stellenbosch University, 2013. http://hdl.handle.net/10019.1/80393.
Full textAbstract:
Thesis (MSc)--Stellenbosch University, 2013.<br>ENGLISH ABSTRACT: The main objective of our study is enumerating spanning trees (G) and perfect matchings
PM(G) on graphs G and lattices L. We demonstrate two methods of enumerating
spanning trees of any connected graph, namely the matrix-tree theorem and as a special
value of the Tutte polynomial T(G; x; y).
We present a general method for counting spanning trees on lattices in d 2 dimensions.
In particular we apply this method on the following regular lattices with d = 2:
rectangular, triangular, honeycomb, kagomé, diced, 9 3 lattice and its dual lattice to
derive a explicit formulas for the number of spanning trees of these lattices of finite sizes.
Regarding the problem of enumerating of perfect matchings, we prove Cayley’s theorem
which relates the Pfaffian of a skew symmetric matrix to its determinant. Using
this and defining the Pfaffian orientation on a planar graph, we derive explicit formula for
the number of perfect matchings on the following planar lattices; rectangular, honeycomb
and triangular.
For each of these lattices, we also determine the bulk limit or thermodynamic limit,
which is a natural measure of the rate of growth of the number of spanning trees (L)
and the number of perfect matchings PM(L).
An algorithm is implemented in the computer algebra system SAGE to count the
number of spanning trees as well as the number of perfect matchings of the lattices
studied.<br>AFRIKAANSE OPSOMMING: Die hoofdoel van ons studie is die aftelling van spanbome (G) en volkome afparings
PM(G) in grafieke G en roosters L. Ons beskou twee metodes om spanbome in ’n samehangende
grafiek af te tel, naamlik deur middel van die matriks-boom-stelling, en as ’n
spesiale waarde van die Tutte polinoom T(G; x; y).
Ons behandel ’n algemene metode om spanbome in roosters in d 2 dimensies af te
tel. In die besonder pas ons hierdie metode toe op die volgende reguliere roosters met
d = 2: reghoekig, driehoekig, heuningkoek, kagomé, blokkies, 9 3 rooster en sy duale
rooster. Ons bepaal eksplisiete formules vir die aantal spanbome in hierdie roosters van
eindige grootte.
Wat die aftelling van volkome afparings aanbetref, gee ons ’n bewys van Cayley se
stelling wat die Pfaffiaan van ’n skeefsimmetriese matriks met sy determinant verbind.
Met behulp van hierdie stelling en Pfaffiaanse oriënterings van planare grafieke bepaal
ons eksplisiete formules vir die aantal volkome afparings in die volgende planare roosters:
reghoekig, driehoekig, heuningkoek.
Vir elk van hierdie roosters word ook die “grootmaat limiet” (of termodinamiese limiet)
bepaal, wat ’n natuurlike maat vir die groeitempo van die aantaal spanbome (L) en die
aantal volkome afparings PM(L) voorstel.
’n Algoritme is in die rekenaaralgebra-stelsel SAGE geimplementeer om die aantal
spanboome asook die aantal volkome afparings in die toepaslike roosters af te tel.
47
Demuynck, Marie-Anne. "Performance Study of Concurrent Search Trees and Hash Algorithms on Multiprocessors Systems." Thesis, University of North Texas, 1996. https://digital.library.unt.edu/ark:/67531/metadc332828/.
Full textAbstract:
This study examines the performance of concurrent algorithms for B-trees and linear hashing. B-trees are widely used as an access method for large, single key, database files, stored in lexicographic order on secondary storage devices. Linear hashing is a fast and reliable hash algorithm, suitable for accessing records stored unordered in buckets. This dissertation presents performance results on implementations of concurrent Bunk-tree and linear hashing algorithms, using lock-based, partitioned and distributed methods on the Sequent Symmetry shared memory multiprocessor system and on a network of distributed processors created with PVM (Parallel Virtual Machine) software. Initial experiments, which started with empty data structures, show good results for the partitioned implementations and lock-based linear hashing, but poor ones for lock-based Blink-trees. A subsequent test, which started with loaded data structures, shows similar results, but with much improved performances for locked Blink- trees. The data also highlighted the high cost of split operations, which reached up to 70% of the total insert time.
48
Sehgal, Rahul. "Greedy routing in a graph by aid of its spanning tree experimental results and analysis /." [Kent, Ohio] : Kent State University, 2009. http://rave.ohiolink.edu/etdc/view?acc%5Fnum=kent1232166476.
Full text
49
Sportiello, Andrea. "Combinatorial methods in Statistical Field Theory : Trees, loops, dimers and orientations vs. Potts and non-linear σ-models". Doctoral thesis, Scuola Normale Superiore, 2010. http://hdl.handle.net/11384/85875.
Full text
50
Lai, Catherine. "A formal framework for linguistic tree query /." Connect to thesis, 2005. http://eprints.unimelb.edu.au/archive/00001594.
Full text