Tesi: "Trees (graph theory)"

1

Dawson, Shelly Jean. "Minimal congestion trees". CSUSB ScholarWorks, 2006. https://scholarworks.lib.csusb.edu/etd-project/3005.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

4

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

5

Humphries, Peter John. "Combinatorial Aspects of Leaf-Labelled Trees". Thesis, University of Canterbury. Mathematics and Statistics, 2008. http://hdl.handle.net/10092/1801.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

7

Tam, Wing Ka. "The strong chromatic index of cubic Halin graphs". HKBU Institutional Repository, 2003. http://repository.hkbu.edu.hk/etd_ra/516.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

8

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

9

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

13

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

15

Okoth, Isaac Owino. "Combinatorics of oriented trees and tree-like structures". Thesis, Stellenbosch : Stellenbosch University, 2015. http://hdl.handle.net/10019.1/96860.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

17

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

Cerca il testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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

Gli stili APA, Harvard, Vancouver, ISO e altri

19

Walvoort, Clayton A. "Peg Solitaire on Trees with Diameter Four". Digital Commons @ East Tennessee State University, 2013. https://dc.etsu.edu/etd/1113.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

21

Jonsson, Jakob. "Simplicial complexes of graphs /". Berlin [u.a.] : Springer, 2008. http://dx.doi.org/10.1007/978-3-540-75858-7.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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

Gli stili APA, Harvard, Vancouver, ISO e altri

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/.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

25

余鳳玲 e 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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

26

王慧霞 e Wai-ha Wong. "Efficient algorithms for broadcast routing". Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 1996. http://hub.hku.hk/bib/B31214733.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

29

Irniger, Christophe-André. "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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

31

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

33

Wang, Yinhua. "Fleet assignment, eulerian subtours and extended steiner trees". Diss., Georgia Institute of Technology, 1995. http://hdl.handle.net/1853/24922.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

35

Jung, Ho-Won. "Direct sparse matrix methods for interior point algorithms". Diss., The University of Arizona, 1990. http://hdl.handle.net/10150/185133.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

36

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

Testo completo

Abstract (sommario):

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

Gli stili APA, Harvard, Vancouver, ISO e altri

37

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

Testo completo

Abstract (sommario):

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

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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

Gli stili APA, Harvard, Vancouver, ISO e altri

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/.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

42

Kwok, Wing-hong, e 郭永康. "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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

43

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

44

Bethlehem, Tobias. "Theory of 3-4 Heap". Thesis, University of Canterbury. Computer Science and Software Engineering, 2008. http://hdl.handle.net/10092/1930.

Testo completo

Abstract (sommario):

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'.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

46

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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/.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

50

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

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Tesi sul tema "Trees (graph theory)"

Cita una fonte nei formati APA, MLA, Chicago, Harvard e in molti altri stili