Spelling suggestions: "subject:"panning trees (graph theory)"" "subject:"panning trees (raph theory)""
1 |
Minors and spanning trees in graphsMontgomery, Richard Harford January 2015 (has links)
No description available.
|
2 |
An approximation algorithm for the maximum leaf spanning arborescence problemDrescher, Matthew. January 1900 (has links)
Thesis (M.Sc.). / Written for the School of Computer Science. Title from title page of PDF (viewed 2008/01/15). Includes bibliographical references.
|
3 |
Network connectivity a tree decomposition approach /Simeone, Daniel. January 1900 (has links)
Thesis (M.Sc.). / Written for the Dept. of Mathematics and Statistics. Title from title page of PDF (viewed 2008/05/29). Includes bibliographical references.
|
4 |
Tree Graphs and Orthogonal Spanning Tree DecompositionsMahoney, James Raymond 17 May 2016 (has links)
Given a graph G, we construct T(G), called the tree graph of G. The vertices of T(G) are the spanning trees of G, with edges between vertices when their respective spanning trees differ only by a single edge. In this paper we detail many new results concerning tree graphs, involving topics such as clique decomposition, planarity, and automorphism groups. We also investigate and present a number of new results on orthogonal tree decompositions of complete graphs.
|
5 |
On the shortest path and minimum spanning tree problemsPettie, Seth 28 August 2008 (has links)
Not available / text
|
6 |
On the shortest path and minimum spanning tree problemsPettie, Seth, January 2003 (has links) (PDF)
Thesis (Ph. D.)--University of Texas at Austin, 2003. / Vita. Includes bibliographical references. Available also from UMI Company.
|
7 |
Enumeration problems on latticesOcansey, Evans Doe 03 1900 (has links)
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.
|
8 |
Approximation algorithms for minimum-cost low-degree subgraphsKönemann, Jochen. January 1900 (has links) (PDF)
Thesis (Ph. D.)--Carnegie Mellon University, 2003. / Title from PDF title page (viewed Dec. 18, 2009). Includes bibliographical references (p. 49-52).
|
9 |
Greedy routing in a graph by aid of its spanning tree experimental results and analysis /Sehgal, Rahul. January 2009 (has links)
Thesis (M.S.)--Kent State University, 2009. / Title from PDF t.p. (viewed Jan. 25, 2010). Advisor: Feodor Dragan. Keywords: greedy routing. Includes bibliographical references (p. 76-77).
|
10 |
Multi-agent based control of large-scale complex systems employing distributed dynamic inference engineZhang, Daili 26 March 2010 (has links)
Increasing societal demand for automation has led to considerable efforts to control large-scale complex systems, especially in the area of autonomous intelligent control methods. The control system of a large-scale complex system needs to satisfy four system level requirements: robustness, flexibility, reusability, and scalability. Corresponding to the four system level requirements, there arise four major challenges. First, it is difficult to get accurate and complete information. Second, the system may be physically highly distributed. Third, the system evolves very quickly. Fourth, emergent global behaviors of the system can be caused by small disturbances at the component level.
The Multi-Agent Based Control (MABC) method as an implementation of distributed intelligent control has been the focus of research since the 1970s, in an effort to solve the above-mentioned problems in controlling large-scale complex systems. However, to the author's best knowledge, all MABC systems for large-scale complex systems with significant uncertainties are problem-specific and thus difficult to extend to other domains or larger systems. This situation is partly due to the control architecture of multiple agents being determined by agent to agent coupling and interaction mechanisms. Therefore, the research objective of this dissertation is to develop a comprehensive, generalized framework for the control system design of general large-scale complex systems with significant uncertainties, with the focus on distributed control architecture design and distributed inference engine design.
A Hybrid Multi-Agent Based Control (HyMABC) architecture is proposed by combining hierarchical control architecture and module control architecture with logical replication rings. First, it decomposes a complex system hierarchically; second, it combines the components in the same level as a module, and then designs common interfaces for all of the components in the same module; third, replications are made for critical agents and are organized into logical rings. This architecture maintains clear guidelines for complexity decomposition and also increases the robustness of the whole system.
Multiple Sectioned Dynamic Bayesian Networks (MSDBNs) as a distributed dynamic probabilistic inference engine, can be embedded into the control architecture to handle uncertainties of general large-scale complex systems. MSDBNs decomposes a large knowledge-based system into many agents. Each agent holds its partial perspective of a large problem domain by representing its knowledge as a Dynamic Bayesian Network (DBN). Each agent accesses local evidence from its corresponding local sensors and communicates with other agents through finite message passing. If the distributed agents can be organized into a tree structure, satisfying the running intersection property and d-sep set requirements, globally consistent inferences are achievable in a distributed way. By using different frequencies for local DBN agent belief updating and global system belief updating, it balances the communication cost with the global consistency of inferences. In this dissertation, a fully factorized Boyen-Koller (BK) approximation algorithm is used for local DBN agent belief updating, and the static Junction Forest Linkage Tree (JFLT) algorithm is used for global system belief updating.
MSDBNs assume a static structure and a stable communication network for the whole system. However, for a real system, sub-Bayesian networks as nodes could be lost, and the communication network could be shut down due to partial damage in the system. Therefore, on-line and automatic MSDBNs structure formation is necessary for making robust state estimations and increasing survivability of the whole system. A Distributed Spanning Tree Optimization (DSTO) algorithm, a Distributed D-Sep Set Satisfaction (DDSSS) algorithm, and a Distributed Running Intersection Satisfaction (DRIS) algorithm are proposed in this dissertation. Combining these three distributed algorithms and a Distributed Belief Propagation (DBP) algorithm in MSDBNs makes state estimations robust to partial damage in the whole system.
Combining the distributed control architecture design and the distributed inference engine design leads to a process of control system design for a general large-scale complex system. As applications of the proposed methodology, the control system design of a simplified ship chilled water system and a notional ship chilled water system have been demonstrated step by step. Simulation results not only show that the proposed methodology gives a clear guideline for control system design for general large-scale complex systems with dynamic and uncertain environment, but also indicate that the combination of MSDBNs and HyMABC can provide excellent performance for controlling general large-scale complex systems.
|
Page generated in 0.1201 seconds