Log in

Relevant bibliographies by topics / Trees (Graph theory) Spanning trees (Graph theory)

Contents

Journal articles
Dissertations / Theses
Books
Book chapters
Conference papers

Academic literature on the topic 'Trees (Graph theory) Spanning trees (Graph theory)'

Author: Grafiati

Published: 4 June 2021

Last updated: 1 February 2022

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

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Trees (Graph theory) Spanning 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.

Journal articles on the topic "Trees (Graph theory) Spanning trees (Graph theory)"

1

JOHANNSEN, DANIEL, MICHAEL KRIVELEVICH, and WOJCIECH SAMOTIJ. "Expanders Are Universal for the Class of All Spanning Trees." Combinatorics, Probability and Computing 22, no. 2 (January 3, 2013): 253–81. http://dx.doi.org/10.1017/s0963548312000533.

Full text

Abstract:

A graph is calleduniversalfor a given graph class(or, equivalently,-universal) if it contains a copy of every graph inas a subgraph. The construction of sparse universal graphs for various classeshas received a considerable amount of attention. There is particular interest in tight-universal graphs, that is, graphs whose number of vertices is equal to the largest number of vertices in a graph from. Arguably, the most studied case is that whenis some class of trees. In this work, we are interested in(n,Δ), the class of alln-vertex trees with maximum degree at most Δ. We show that everyn-vertex graph satisfying certain natural expansion properties is(n,Δ)-universal. Our methods also apply to the case when Δ is some function ofn. Since random graphs are known to be good expanders, our result implies, in particular, that there exists a positive constantcsuch that the random graphG(n,cn−1/3log2n) is asymptotically almost surely (a.a.s.) universal for(n,O(1)). Moreover, a corresponding result holds for the random regular graph of degreecn2/3log2n. Another interesting consequence is the existence of locally sparsen-vertex(n,Δ)-universal graphs. For example, we show that one can (randomly) constructn-vertex(n,O(1))-universal graphs with clique number at most five. This complements the construction of Bhatt, Chung, Leighton and Rosenberg (1989), whose(n,Δ)-universal graphs with merelyO(n)edges contain large cliques of size Ω(Δ). Finally, we show that random graphs are robustly(n,Δ)-universal in the context of the Maker–Breaker tree-universality game.

APA, Harvard, Vancouver, ISO, and other styles

2

Janson, Svante. "Random trees in a graph and trees in a random graph." Mathematical Proceedings of the Cambridge Philosophical Society 100, no. 2 (September 1986): 319–30. http://dx.doi.org/10.1017/s0305004100066111.

Full text

Abstract:

This paper treats two related sets of problems in the theory of random graphs. In Sections 2 and 3 we study random spanning subtrees of a complete graph (or, equivalently, random labelled trees). It is shown that the number of common edges of two such random trees asymptotically has a Poisson distribution with expectation 2. Similar results are obtained for the number of edges in the intersection or union of more than two random trees.

APA, Harvard, Vancouver, ISO, and other styles

3

DARMANN, ANDREAS. "POPULAR SPANNING TREES." International Journal of Foundations of Computer Science 24, no. 05 (August 2013): 655–77. http://dx.doi.org/10.1142/s0129054113500226.

Full text

Abstract:

Combinatorial Optimization is combined with Social Choice Theory when the goal is to decide on the quality of a spanning tree of an undirected graph. Given individual preferences over the edges of the graph, spanning trees are compared by means of a Condorcet criterion. The comparisons are based on scoring functions used in classic voting rules such as approval voting and Borda voting. In this work, we investigate the computational complexity involved in deciding on the quality of a spanning tree with respect to the different voting rules adapted. In particular, we draw the sharp separation line between polynomially solvable and computationally intractable instances.

APA, Harvard, Vancouver, ISO, and other styles

4

Li, Feng. "The Number of Spanning Trees in the Composition Graphs." Mathematical Problems in Engineering 2014 (2014): 1–5. http://dx.doi.org/10.1155/2014/613685.

Full text

Abstract:

Using the composition of some existing smaller graphs to construct some large graphs, the number of spanning trees and the Laplacian eigenvalues of such large graphs are also closely related to those of the corresponding smaller ones. By using tools from linear algebra and matrix theory, we establish closed formulae for the number of spanning trees of the composition of two graphs with one of them being an arbitrary complete 3-partite graph and the other being an arbitrary graph. Our results extend some of the previous work, which depend on the structural parameters such as the number of vertices and eigenvalues of the small graphs only.

APA, Harvard, Vancouver, ISO, and other styles

5

Boaventura-Netto, Paulo Oswaldo. "Ranking graph edges by the weight of their spanning arborescences or trees." Pesquisa Operacional 28, no. 1 (April 2008): 59–73. http://dx.doi.org/10.1590/s0101-74382008000100004.

Full text

Abstract:

A result based on a classic theorem of graph theory is generalized for edge-valued graphs, allowing determination of the total value of the spanning arborescences with a given root and containing a given arc in a directed valued graph. A corresponding result for undirected valued graphs is also presented. In both cases, the technique allows for a ranking of the graph edges by importance under this criterion. This ranking is proposed as a tool to determine the relative importance of the edges of a graph in network vulnerability studies. Some examples of application are presented.

APA, Harvard, Vancouver, ISO, and other styles

6

Vasconcellos, Jucele França de Alencar, Edson Norberto Cáceres, Henrique Mongelli, Siang Wun Song, Frank Dehne, and Jayme Luiz Szwarcfiter. "New BSP/CGM algorithms for spanning trees." International Journal of High Performance Computing Applications 33, no. 3 (October 14, 2018): 444–61. http://dx.doi.org/10.1177/1094342018803672.

Full text

Abstract:

Computing a spanning tree (ST) and a minimum ST (MST) of a graph are fundamental problems in graph theory and arise as a subproblem in many applications. In this article, we propose parallel algorithms to these problems. One of the steps of previous parallel MST algorithms relies on the heavy use of parallel list ranking which, though efficient in theory, is very time-consuming in practice. Using a different approach with a graph decomposition, we devised new parallel algorithms that do not make use of the list ranking procedure. We proved that our algorithms are correct, and for a graph [Formula: see text], [Formula: see text], and [Formula: see text], the algorithms can be executed on a Bulk Synchronous Parallel/Coarse Grained Multicomputer (BSP/CGM) model using [Formula: see text] communications rounds with [Formula: see text] computation time for each round. To show that our algorithms have good performance on real parallel machines, we have implemented them on graphics processing unit. The obtained speedups are competitive and showed that the BSP/CGM model is suitable for designing general purpose parallel algorithms.

APA, Harvard, Vancouver, ISO, and other styles

7

LI, WENBO V., and XINYI ZHANG. "On the Difference of Expected Lengths of Minimum Spanning Trees." Combinatorics, Probability and Computing 18, no. 3 (May 2009): 423–34. http://dx.doi.org/10.1017/s0963548308009590.

Full text

Abstract:

An exact formula for the expected length of the minimum spanning tree of a connected graph, with independent and identical edge distribution, is given, which generalizes Steele's formula in the uniform case. For a complete graph, the difference of expected lengths between exponential distribution, with rate one, and uniform distribution on the interval (0, 1) is shown to be positive and of rate ζ(3)/n. For wheel graphs, precise values of expected lengths are given via calculations of the associated Tutte polynomials.

APA, Harvard, Vancouver, ISO, and other styles

8

Shang, Yilun. "On the number of spanning trees, the Laplacian eigenvalues, and the Laplacian Estrada index of subdivided-line graphs." Open Mathematics 14, no. 1 (January 1, 2016): 641–48. http://dx.doi.org/10.1515/math-2016-0055.

Full text

Abstract:

Abstract As a generalization of the Sierpiński-like graphs, the subdivided-line graph Г(G) of a simple connected graph G is defined to be the line graph of the barycentric subdivision of G. In this paper we obtain a closed-form formula for the enumeration of spanning trees in Г(G), employing the theory of electrical networks. We present bounds for the largest and second smallest Laplacian eigenvalues of Г(G) in terms of the maximum degree, the number of edges, and the first Zagreb index of G. In addition, we establish upper and lower bounds for the Laplacian Estrada index of Г(G) based on the vertex degrees of G. These bounds are also connected with the number of spanning trees in Г(G).

APA, Harvard, Vancouver, ISO, and other styles

9

KOMLÓS, JÁNOS, GÁBOR N. SÁRKÓZY, and ENDRE SZEMERÉDI. "Spanning Trees in Dense Graphs." Combinatorics, Probability and Computing 10, no. 5 (September 2001): 397–416. http://dx.doi.org/10.1017/s0963548301004849.

Full text

Abstract:

In this paper we prove the following almost optimal theorem. For any δ > 0, there exist constants c and n0 such that, if n [ges ] n0, T is a tree of order n and maximum degree at most cn/log n, and G is a graph of order n and minimum degree at least (1/2 + δ)n, then T is a subgraph of G.

APA, Harvard, Vancouver, ISO, and other styles

10

Gavril, Fǎnicǎ. "Generating the maximum spanning trees of a weighted graph." Journal of Algorithms 8, no. 4 (December 1987): 592–97. http://dx.doi.org/10.1016/0196-6774(87)90053-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

More sources

Dissertations / Theses on the topic "Trees (Graph theory) Spanning trees (Graph theory)"

1

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

2

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

3

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

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

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

6

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

7

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

8

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

9

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

10

Zhang, Daili. "Multi-agent based control of large-scale complex systems employing distributed dynamic inference engine." Diss., Georgia Institute of Technology, 2010. http://hdl.handle.net/1853/33963.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

More sources

Books on the topic "Trees (Graph theory) Spanning trees (Graph theory)"

1

Leister, Karen J. Using minimal spanning trees to compare the reliability of network topologies. Hampton, Va: Langley Research Center, 1990.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

2

Indian Institute of Management, Ahemdabad., ed. A probabilistic tabu search algorithm for the generalized minimum spanning tree problem. Ahmedabad: Indian Institute of Management, 2003.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

3

Leister, Karen J. Using minimal spanning trees to compare the reliabilty of network topologies. [Washington, DC]: National Aeronautics and Space Administration, Office of Management, Scientific and Technical Information Division, 1990.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

4

Indian Institute of Management, Ahmedabad., ed. Solving medium to large sized euclidean generalized minimum spanning tree problems. Ahmedabad: Indian Institute of Management, 2003.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

5

Limnios, N. Fault trees. London, UK: ISTE, 2007.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

6

Kasʹi͡anov, V. N. Graph theory for programmers: Algorithms for processing trees. Dordrecht: Kluwer Academic, 2000.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

7

A, Evstigneev V., ed. Graph theory for programmers: Algorithms for processing trees. Dordrecht: Kluwer Academic, 2000.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

8

Introduction to [lambda]-trees. Singapore: World Scientific, 2001.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

9

Crouch, Peter. Trees, bialgebras and intrinsic numerical algorithms. Chicago, IL: Dept. of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, 1990.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

10

Rubin, Matatyahu. The reconstruction of trees from their automorphism groups. Providence, R.I: American Mathematical Society, 1993.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

More sources

Book chapters on the topic "Trees (Graph theory) Spanning trees (Graph theory)"

1

Kasyanov, Victor N., and Viadimir A. Evstigneev. "Spanning Trees." In Graph Theory for Programmers, 121–73. Dordrecht: Springer Netherlands, 2000. http://dx.doi.org/10.1007/978-94-011-4122-2_3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Hartsfield, N., and J. S. Werth. "Spanning Trees of the Complete Bipartite Graph." In Topics in Combinatorics and Graph Theory, 339–46. Heidelberg: Physica-Verlag HD, 1990. http://dx.doi.org/10.1007/978-3-642-46908-4_38.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Leaños, J., C. Merino, G. Salazar, and J. Urrutia. "Spanning Trees of Multicoloured Point Sets with Few Intersections." In Combinatorial Geometry and Graph Theory, 113–22. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/978-3-540-30540-8_13.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Keller, Chaya, Micha A. Perles, Eduardo Rivera-Campo, and Virginia Urrutia-Galicia. "Blockers for Noncrossing Spanning Trees in Complete Geometric Graphs." In Thirty Essays on Geometric Graph Theory, 383–97. New York, NY: Springer New York, 2012. http://dx.doi.org/10.1007/978-1-4614-0110-0_20.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Hamacher, Horst W., and Kathrin Klamroth. "Introduction to Graph Theory and Shortest Spanning Trees." In Lineare und Netzwerk-Optimierung / Linear and Network-Optimization, 105–16. Wiesbaden: Vieweg+Teubner Verlag, 2000. http://dx.doi.org/10.1007/978-3-322-91579-5_5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Clemens, Dennis, Asaf Ferber, Roman Glebov, Dan Hefetz, and Anita Liebenau. "Building spanning trees quickly in Maker-Breaker games." In The Seventh European Conference on Combinatorics, Graph Theory and Applications, 365–70. Pisa: Scuola Normale Superiore, 2013. http://dx.doi.org/10.1007/978-88-7642-475-5_58.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Huemer, Clemens, and Anna de Mier. "An improved lower bound on the maximum number of non-crossing spanning trees." In The Seventh European Conference on Combinatorics, Graph Theory and Applications, 283–90. Pisa: Scuola Normale Superiore, 2013. http://dx.doi.org/10.1007/978-88-7642-475-5_46.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Saoub, Karin R. "Trees." In Graph Theory, 123–68. Boca Raton: CRC Press, 2021. | Series: Textbooks in mathematics: Chapman and Hall/CRC, 2021. http://dx.doi.org/10.1201/9781138361416-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Sumner, David. "Forbidden Trees." In Graph Theory, 69–89. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-97686-0_8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Gimadi, Edward Kh, Aleksandr S. Shevyakov, and Alexandr A. Shtepa. "On Asymptotically Optimal Approach for the Problem of Finding Several Edge-Disjoint Spanning Trees of Given Diameter in an Undirected Graph with Random Edge Weights." In Mathematical Optimization Theory and Operations Research, 67–78. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-77876-7_5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Trees (Graph theory) Spanning trees (Graph theory)"

1

Onete, Cristian E., and A. Maria Cristina C. Onete. "Finding spanning trees and Hamiltonian circuits in an un-oriented graph an algebraic approach." In 2011 European Conference on Circuit Theory and Design (ECCTD). IEEE, 2011. http://dx.doi.org/10.1109/ecctd.2011.6043384.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Zhou, Hong, and Kwun-Lon Ting. "Spanning Tree Based Topological Optimization of Compliant Mechanisms." In ASME 2005 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. ASMEDC, 2005. http://dx.doi.org/10.1115/detc2005-84608.

Full text

Abstract:

In graph theory, spanning trees connect all the vertices together using minimum number of edges. A topological optimization method of compliant mechanisms is presented based on spanning tree theory. A valid topology is regarded as a network connecting input, output, support and intermediate nodes, which contains at least one spanning tree among the introduced nodes. Invalid disconnected topologies can be weeded out if no spanning tree is included. No further deformation analysis and performance evaluation is needed for invalid disconnected topologies. Problem-dependent objectives are optimized for topological optimization of compliant mechanisms. Constraints about maximum input displacement and input force, maximum stress and overlapping connections are directly imposed during the optimization process. The discrete optimization problem is solved by genetic algorithm with penalty function handling constraints. An example is presented to verify the effectiveness of the proposed optimization procedure.

APA, Harvard, Vancouver, ISO, and other styles

3

Dreher, D., and J. L. Walker. "Connections between computation trees and graph covers." In 2009 Information Theory and Applications Workshop (ITA). IEEE, 2009. http://dx.doi.org/10.1109/ita.2009.5044971.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Dadalto, Arthur Pratti, Fábio Luiz Usberti, and Mário César San Felice. "On the Approximability of the Minimum Subgraph Diameter Problem." In III Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2018. http://dx.doi.org/10.5753/etc.2018.3169.

Full text

Abstract:

This work addresses the minimum subgraph diameter problem (MSDP) by answering an open question with respect to its approximability. Given a graph with lengths and costs associated to its edges, the MSDP consists in finding a spanning subgraph with total cost limited by a given budget, such that its diameter is minimum. We prove that there is no -approximation algorithm for the MSDP, for any constant , unless P = NP. Our proof is grounded on the non-approximability of the minimum spanning tree diameter problem, proven by Bálint in 2013.

APA, Harvard, Vancouver, ISO, and other styles

5

Zou, Hong-Liu, Karim Abdel-Malek, and Jia-Yi Wang. "Numerical Formulations for Computing Design Propagations of the Spatial Slider-Crank Mechanism." In ASME 1996 Design Engineering Technical Conferences and Computers in Engineering Conference. American Society of Mechanical Engineers, 1996. http://dx.doi.org/10.1115/96-detc/mech-1198.

Full text

Abstract:

Abstract A numerical formulation for studying the design of a spatial slider-crank mechanism is developed and illustrated. The mechanism is modeled using graph theory and closed loops are converted to a spanning tree structure by cutting joints and introducing new constraints. Variations of these constraints with respect to design parameters are derived. A change in link length or link orientation is propagated through the model and a new assembled configuration is computed hence redesigning the mechanism. Constraints are formulated in Cartesian space but computed in relative joint coordinate space. The Jacobian of the constraint is transformed to joint coordinate space in order to compute an assembled configuration for the cut-joint constraint formulation. The experimental code is illustrated through numerical examples where joint-position vectors and orientation matrices are altered.

APA, Harvard, Vancouver, ISO, and other styles

6

Li, Bohan, Xindi Zhang, Shaowei Cai, Jinkun Lin, Yiyuan Wang, and Christian Blum. "NuCDS: An Efficient Local Search Algorithm for Minimum Connected Dominating Set." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/209.

Full text

Abstract:

The minimum connected dominating set (MCDS) problem is an important extension of the minimum dominating set problem, with wide applications, especially in wireless networks. Despite its practical importance, there are few works on solving MCDS for massive graphs, mainly due to the complexity of maintaining connectivity. In this paper, we propose two novel ideas, and develop a new local search algorithm for MCDS called NuCDS. First, a hybrid dynamic connectivity maintenance method is designed to switch alternately between a novel fast connectivity maintenance method based on spanning tree and its previous counterpart. Second, we define a new vertex property called \emph{safety} to make the algorithm more considerate when selecting vertices. Experiments show that NuCDS significantly outperforms the state-of-the-art MCDS algorithms on both massive graphs and classic benchmarks.

APA, Harvard, Vancouver, ISO, and other styles

7

Yan, Hong-Sen, Feng-Ming Ou, and Ming-Feng Tang. "An Algorithm for the Enumeration of Serial and/or Parallel Combinations of Kinematic Building Blocks." In ASME 2004 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. ASMEDC, 2004. http://dx.doi.org/10.1115/detc2004-57295.

Full text

Abstract:

An algorithm is presented, based on graph theory, for enumerating all feasible serial and/or parallel combined mechanisms from the given rotary or translational power source and specific kinematic building blocks. Through the labeled out-tree representations for the configurations of combined mechanisms, the enumeration procedure is developed by adapting the algorithm for the enumeration of trees. A rotary power source and four kinematic building blocks: a crank-rocker linkage, a rack-pinion, a double-slider mechanism, and a cam-follower mechanism, are chosen as the combination to illustrate the algorithm. And, two examples are provided to validate the algorithm.

APA, Harvard, Vancouver, ISO, and other styles

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!