Relevant bibliographies by topics / Trees (graph theory) / Dissertations / Theses
To see the other types of publications on this topic, follow the link: Trees (graph theory).

Dissertations / Theses on the topic 'Trees (graph theory)'

Author: Grafiati
Published: 4 June 2021
Last updated: 25 July 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
4

Mahoney, James Raymond. "Tree Graphs and Orthogonal Spanning Tree Decompositions." PDXScholar, 2016. http://pdxscholar.library.pdx.edu/open_access_etds/2944.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
8

Jayasooriya, Arachchilage Dinush Lanka Panditharathna. "Spanning Trees of Certain Types." OpenSIUC, 2016. https://opensiuc.lib.siu.edu/theses/2049.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
9

Curran, Sean P. "Independent trees in 4-connected graphs." Diss., Georgia Institute of Technology, 2003. http://hdl.handle.net/1853/29842.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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.
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).
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.
APA, Harvard, Vancouver, ISO, and other styles
13

Chan, Wai Hong. "Bandwidth problems of graphs." HKBU Institutional Repository, 1996. http://repository.hkbu.edu.hk/etd_ra/62.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
Thesis (PhD)--Stellenbosch University, 2015.
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.
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.
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
Let 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.
APA, Harvard, Vancouver, ISO, and other styles
17

Lee, William W. L. (William Wai Lam) Carleton University Dissertation Computer Science. "Tree editing algorithms." Ottawa, 1992.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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.
Science, Faculty of
Computer Science, Department of
Graduate
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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.
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).
Ph.D.
Doctorate
Electrical Engineering and Computer Science
Engineering and Computer Science
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
31

Razanajatovo, Misanantenaina Valisoa. "Properties of greedy trees." Thesis, Stellenbosch : Stellenbosch University, 2014. http://hdl.handle.net/10019.1/95909.

Full text
Abstract:
Thesis (MSc)--Stellenbosch University, 2014.
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.
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.
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
University of Central Florida College of Engineering Thesis
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 .
Ph.D.
School of Electrical Engineering and Computer Science
Engineering and Computer Science
Electrical Engineering and Computer Science
172 p.
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
36

Wilson, Keith Eirik. "Factoring Semiprimes Using PG2N Prime Graph Multiagent Search." PDXScholar, 2011. https://pdxscholar.library.pdx.edu/open_access_etds/219.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
37

Lattanzi, Mark R. "Table-driven quadtree traversal algorithms." Thesis, Virginia Tech, 1989. http://hdl.handle.net/10919/44120.

Full text
Abstract:
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.
Master of Science
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:

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.


Master of Science
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
43

Bedrax-Weiss, Tania. "Optimal search protocols /." view abstract or download file of text, 1999. http://wwwlib.umi.com/cr/uoregon/fullcit?p9948016.

Full text
Abstract:
Thesis (Ph. D.)--University of Oregon, 1999.
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.
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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'.
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
Thesis (MComm) -- Stellenbosch University, 2002.
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.
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.
APA, Harvard, Vancouver, ISO, and other styles
46

Ocansey, Evans Doe. "Enumeration problems on lattices." Thesis, Stellenbosch : Stellenbosch University, 2013. http://hdl.handle.net/10019.1/80393.

Full text
Abstract:
Thesis (MSc)--Stellenbosch University, 2013.
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.
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.
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
50

Lai, Catherine. "A formal framework for linguistic tree query /." Connect to thesis, 2005. http://eprints.unimelb.edu.au/archive/00001594.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the bibliographies on the topic 'Trees (graph theory)' for other source types:
Journal articles Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography