Academic literature on the topic 'Directed spanning tree'

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 'Directed spanning tree.'

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 "Directed spanning tree"

1

Bhatt, Abhay G., and Rahul Roy. "On a random directed spanning tree." Advances in Applied Probability 36, no. 1 (2004): 19–42. http://dx.doi.org/10.1239/aap/1077134462.

Full text
Abstract:
We study the asymptotic properties of a minimal spanning tree formed by n points uniformly distributed in the unit square, where the minimality is amongst all rooted spanning trees with a direction of growth. We show that the number of branches from the root of this tree, the total length of these branches, and the length of the longest branch each converges weakly. This model is related to the study of record values in the theory of extreme-value statistics and this relation is used to obtain our results. The results also hold when the tree is formed from a Poisson point process of intensity n in the unit square.
APA, Harvard, Vancouver, ISO, and other styles
2

Bhatt, Abhay G., and Rahul Roy. "On a random directed spanning tree." Advances in Applied Probability 36, no. 01 (2004): 19–42. http://dx.doi.org/10.1017/s0001867800012854.

Full text
Abstract:
We study the asymptotic properties of a minimal spanning tree formed by n points uniformly distributed in the unit square, where the minimality is amongst all rooted spanning trees with a direction of growth. We show that the number of branches from the root of this tree, the total length of these branches, and the length of the longest branch each converges weakly. This model is related to the study of record values in the theory of extreme-value statistics and this relation is used to obtain our results. The results also hold when the tree is formed from a Poisson point process of intensity n in the unit square.
APA, Harvard, Vancouver, ISO, and other styles
3

Sun, Zong Hai, and Fu You Feng. "Pinning Control on Directed Complex Network via Identifying Spanning Trees." Applied Mechanics and Materials 220-223 (November 2012): 1487–90. http://dx.doi.org/10.4028/www.scientific.net/amm.220-223.1487.

Full text
Abstract:
Previous works had proved that a directed complex network could be pinned to its equilibrium by a single controller if it had a spanning tree. But in fact, most of the real networks do not have spanning tree. In this paper, we study the pinning control of a general directed network without spanning tree. We prove that a general network could be divided into some sub-networks with spanning trees, and then the aggregation network is stabilized by stabilizing every sub-network with a single controller. As an illustrative example, a network without spanning tree is simulated to verify the effectiveness and convenience with the selective pinning control strategy.
APA, Harvard, Vancouver, ISO, and other styles
4

Nurdiyanto, Tito, and Ely Susanti. "Spanning-Tree pada Graf Berarah dengan Matriks In-Degree." Jurnal Edukasi dan Sains Matematika (JES-MAT) 5, no. 1 (2019): 1. http://dx.doi.org/10.25134/jes-mat.v5i1.1650.

Full text
Abstract:
ABSTRACTGraph has a concept of tree. Tree is a connected graph which is not consist cycle. Concept of tree is an important concept because it can be used to support application of graph in any variation of science. Besides, spanning-tree is a tree in graph with every point on graph. Every graph can be formed at least there is one spanning tree. The problem of this article is how to determine the sum of spanning-tree in directed graph with matrix in-degree yang menggunakan teorema: the value of the cofactor of is equal to the number of arborescence in rooted at the vertex . Arborescence in is spanning arborescence.Keywords : spanning-tree, directed graph, matrix in-degreeABSTRAKGraf memiliki konsep tree (pohon). Tree merupakan graf terhubung yang tidak memuat siklus. Konsep tree merupakan konsep yang penting karena konsep ini dapat digunakan untuk mendukung penerapan graf dalam berbagai bidang ilmu. Sedangkan spanning-tree adalah sebuah pohon pada graf yang memuat semua titik di . Dari setiap graf dapat dibentuk paling sedikit sebuah spanning-tree. Permasalahan dalam artikel ini adalah bagaimana menentukan jumlah spanning-tree pada graf berarah dengan matriks in-degree yang menggunakan teorema: nilai kofaktor dari adalah sama dengan banyaknya arborescence pada dengan titik sebagai root. Arborescence pada juga merupakan spanning arborescence.Kata kunci: spanning-tree, graf berarah, matriks in-degree
APA, Harvard, Vancouver, ISO, and other styles
5

Lokshtanov, Daniel, Venkatesh Raman, Saket Saurabh, and Somnath Sikdar. "On the directed Full Degree Spanning Tree problem." Discrete Optimization 8, no. 1 (2011): 97–109. http://dx.doi.org/10.1016/j.disopt.2010.09.001.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Wang, Zhuoran, Dian Ouyang, Yikun Wang, Qi Liang, and Zhuo Huang. "Efficient and Effective Directed Minimum Spanning Tree Queries." Mathematics 11, no. 9 (2023): 2200. http://dx.doi.org/10.3390/math11092200.

Full text
Abstract:
Computing directed Minimum Spanning Tree (DMST) is a fundamental problem in graph theory. It is applied in a wide spectrum of fields from computer network and communication protocol design to revenue maximization in social networks and syntactic parsing in Natural Language Processing. State-of-the-art solutions are online algorithms that compute DMST for a given graph and a root. For multi-query requirements, the online algorithm is inefficient. To overcome the drawbacks, in this paper, we propose an indexed approach that reuses the computation result to facilitate single and batch queries. We store all the potential edges of DMST in a hierarchical tree in O(n) space complexity. Furthermore, we answer the DMST query of any root in O(n) time complexity. Experimental results demonstrate that our approach can achieve a speedup of 2–3 orders of magnitude in query processing compared to the state-of-the-art while consuming O(n) index size.
APA, Harvard, Vancouver, ISO, and other styles
7

Choi, Myeong-Bok, and Sang-Un Lee. "A Prim Minimum Spanning Tree Algorithm for Directed Graph." Journal of the Institute of Webcasting, Internet and Telecommunication 12, no. 3 (2012): 51–61. http://dx.doi.org/10.7236/jiwit.2012.12.3.51.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Fujiyoshi, Akio. "Recognition of directed acyclic graphs by spanning tree automata." Theoretical Computer Science 411, no. 38-39 (2010): 3493–506. http://dx.doi.org/10.1016/j.tcs.2010.06.006.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

LIAO, CHUNG-SHOU, and LOUXIN ZHANG. "APPROXIMATING THE SPANNING k-TREE FOREST PROBLEM." International Journal of Foundations of Computer Science 23, no. 07 (2012): 1543–54. http://dx.doi.org/10.1142/s0129054112500232.

Full text
Abstract:
The spanning star forest problem is an interesting algorithmic problem in combinatorial optimization and finds different applications. We generalize it into the spanning k-tree forest problem, which is to find a maximum spanning forest in which each tree component has a central vertex and other vertices in the component have distance at most k away from the central vertex. We show that this new problem can be approximated with ratio [Formula: see text] in polynomial time for both undirected and directed graphs. In the weighted distance model, a ½-approximation algorithm is presented for it.
APA, Harvard, Vancouver, ISO, and other styles
10

Penrose, Mathew D., and Andrew R. Wade. "Random minimal directed spanning trees and Dickman-type distributions." Advances in Applied Probability 36, no. 3 (2004): 691–714. http://dx.doi.org/10.1239/aap/1093962229.

Full text
Abstract:
In Bhatt and Roy's minimal directed spanning tree construction for n random points in the unit square, all edges must be in a south-westerly direction and there must be a directed path from each vertex to the root placed at the origin. We identify the limiting distributions (for large n) for the total length of rooted edges, and also for the maximal length of all edges in the tree. These limit distributions have been seen previously in analysis of the Poisson-Dirichlet distribution and elsewhere; they are expressed in terms of Dickman's function, and their properties are discussed in some detail.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Directed spanning tree"

1

Římský, Adam. "Využití teorie grafů pro návrh a optimalizaci architektur datových sítí." Master's thesis, Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií, 2010. http://www.nusl.cz/ntk/nusl-218337.

Full text
Abstract:
This masters'sthesis deals with graph theory and utilization of this theory for design and optimization of data network structures. Introduction chapter describes graph theory in general view, i.e. fundamental terms used for graph description, graph distinguishing, etc. Next part describes graph algorithms, for example a shortest path finding. After this I write about actual routing protocols where the graph algorithms are used. Last but one part deals with queuing theory and final part describes practical presentation of using graph theory for design and optimization of data network structure in Matlab programme environment.
APA, Harvard, Vancouver, ISO, and other styles
2

Jakel, Roland. "Lineare und nichtlineare Analyse hochdynamischer Einschlagvorgänge mit Creo Simulate und Abaqus/Explicit." Universitätsbibliothek Chemnitz, 2015. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-171812.

Full text
Abstract:
Der Vortrag beschreibt wie sich mittels der unterschiedlichen Berechnungsverfahren zur Lösung dynamischer Strukturpobleme der Einschlag eines idealisierten Bruchstücks in eine Schutzwand berechnen lässt. Dies wird mittels zweier kommerzieller FEM-Programme beschrieben: a.) Creo Simulate nutzt zur Lösung die Methode der modalen Superposition, d.h., es können nur lineare dynamische Systeme mit rein modaler Dämpfung berechnet werden. Kontakt zwischen zwei Bauteilen lässt sich damit nicht erfassen. Die unbekannte Kraft-Zeit-Funktion des Einschlagvorganges muss also geeignet abgeschätzt und als äußere Last auf die Schutzwand aufgebracht werden. Je dynamischer der Einschlagvorgang, desto eher wird der Gültigkeitsbereich des zugrunde liegenden linearen Modells verlassen. b.) Abaqus/Explicit nutzt ein direktes Zeitintegrationsverfahren zur schrittweisen Lösung der zugrunde liegenden Differentialgleichung, die keine tangentiale Steifigkeitsmatrix benötigt. Damit können sowohl Materialnichtlinearitäten als auch Kontakt geeignet erfasst und damit die Kraft-Zeit-Funktion des Einschlages ermittelt werden. Auch bei extrem hochdynamischen Vorgängen liefert diese Methode ein gutes Ergebnis. Es müssen dafür jedoch weit mehr Werkstoffdaten bekannt sein, um das nichtlineare elasto-plastische Materialverhalten mit Schädigungseffekten korrekt zu beschreiben. Die Schwierigkeiten der Werkstoffdatenbestimmung werden in den Grundlagen erläutert<br>The presentation describes how to analyze the impact of an idealized fragment into a stell protective panel with different dynamic analysis methods. Two different commercial Finite Element codes are used for this: a.) Creo Simulate: This code uses the method of modal superposition for analyzing the dynamic response of linear dynamic systems. Therefore, only modal damping and no contact can be used. The unknown force-vs.-time curve of the impact event cannot be computed, but must be assumed and applied as external force to the steel protective panel. As more dynamic the impact, as sooner the range of validity of the underlying linear model is left. b.) Abaqus/Explicit: This code uses a direct integration method for an incremental (step by step) solution of the underlying differential equation, which does not need a tangential stiffness matrix. In this way, matieral nonlinearities as well as contact can be obtained as one result of the FEM analysis. Even for extremely high-dynamic impacts, good results can be obtained. But, the nonlinear elasto-plastic material behavior with damage initiation and damage evolution must be characterized with a lot of effort. The principal difficulties of the material characterization are described
APA, Harvard, Vancouver, ISO, and other styles
3

Yin, Zong-Yau, and 尹宗耀. "An Algorithm for Enumerating All Spanning Trees of a Directed Graph." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/90515151772538570217.

Full text
Abstract:
碩士<br>國立清華大學<br>資訊工程學系<br>91<br>Let G = (V, E) be a directed graph with vertex set V and edge set E. A directed spanning tree of G rooted at a vertex r is a spanning tree of G having a unique path from r to every other vertex. In this thesis, by using Kapoor and Ramesh’s [8] “edge-exchange” technique, we propose an O(Nnlogn + n^2 + nm) time algorithm for enumerating all spanning trees of a directed graph. The output size of our algorithm is O(N + n^2) that is the same as Kapoor and Ramesh’s algorithm in [8]. Furthermore, although our algorithm is slightly slower than Kapoor and Ramesh’s, the space complexity of our algorithm is O(n + m), which is optimal.
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Directed spanning tree"

1

Krishnan, Radha, and Balaji Raghavachari. "The Directed Minimum-Degree Spanning Tree Problem." In FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science. Springer Berlin Heidelberg, 2001. http://dx.doi.org/10.1007/3-540-45294-x_20.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Lee, Hung-Yeh, Hsuan-Yu Liao, and Wing-Kai Hon. "Colored Constrained Spanning Tree on Directed Graphs." In Lecture Notes in Computer Science. Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-38906-1_37.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Lokshtanov, Daniel, Venkatesh Raman, Saket Saurabh, and Somnath Sikdar. "On the Directed Degree-Preserving Spanning Tree Problem." In Parameterized and Exact Computation. Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-11269-0_23.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Saha, Kumarjit. "Directed Spanning Forest for Ginibre Ensemble Is a Tree." In Indian Statistical Institute Series. Springer Nature Singapore, 2024. http://dx.doi.org/10.1007/978-981-99-9994-1_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Fujiyoshi, Akio. "Recognition of a Spanning Tree of Directed Acyclic Graphs by Tree Automata." In Implementation and Application of Automata. Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-02979-0_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Binkele-Raible, Daniel, and Henning Fernau. "A Faster Exact Algorithm for the Directed Maximum Leaf Spanning Tree Problem." In Computer Science – Theory and Applications. Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-13182-0_31.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Sadhukhan, Sounak, and Samar Sen Sarma. "A Solution of Degree Constrained Spanning Tree Using Hybrid GA with Directed Mutation." In Smart Innovation, Systems and Technologies. Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-07353-8_75.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Das, Asit Kumar, Shampa Sengupta, and Saikat Chakrabarty. "Reduct Generation by Formation of Directed Minimal Spanning Tree Using Rough Set Theory." In Advances in Intelligent and Soft Computing. Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-27443-5_15.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Pollatos, Gerasimos G., Orestis A. Telelis, and Vassilis Zissimopoulos. "Updating Directed Minimum Cost Spanning Trees." In Experimental Algorithms. Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11764298_27.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Böther, Maximilian, Otto Kißig, and Christopher Weyand. "Efficiently Computing Directed Minimum Spanning Trees." In 2023 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics, 2023. http://dx.doi.org/10.1137/1.9781611977561.ch8.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Directed spanning tree"

1

The, Hieu Tran, and Nattapong Kitsuwan. "Optimizing Directed Spanning Trees for Enhanced Tolerance to Multiple Link Failures in SDN." In 2024 IEEE Opto-Electronics and Communications Conference (OECC). IEEE, 2024. https://doi.org/10.1109/oecc54135.2024.10975492.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Yue, Dongdong, Simone Baldi, and Jinde Cao. "Distributed Adaptive Consensus Disturbance Rejection: a Directed-spanning-tree Perspective." In 2022 41st Chinese Control Conference (CCC). IEEE, 2022. http://dx.doi.org/10.23919/ccc55666.2022.9902382.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Harrigan, M., and P. Healy. "Efficiently drawing a significant spanning tree of a directed graph." In Asia-Pacific Symposium on Visualisation 2007. IEEE, 2007. http://dx.doi.org/10.1109/apvis.2007.329275.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Xu, Kaihua, Yuhua Liu, Hao Huang, and Haiyan Zhu. "Research of Directed Network Capacity Expansion Based on Spanning Tree Diagram." In Third International Conference on Natural Computation (ICNC 2007) Vol V. IEEE, 2007. http://dx.doi.org/10.1109/icnc.2007.609.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Ji, Peng, Chengdong Wu, Yunzhou Zhang, and Zixi Jia. "Research of Directed Spanning Tree Routing Protocol for Wireless Sensor Networks." In 2007 International Conference on Mechatronics and Automation. IEEE, 2007. http://dx.doi.org/10.1109/icma.2007.4303755.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Ikuta, Takuto, and Takuya Akiba. "Integer programming approach for directed minimum spanning tree problem on temporal graphs." In SIGMOD/PODS'16: International Conference on Management of Data. ACM, 2016. http://dx.doi.org/10.1145/2980523.2980528.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Chen, Yangzhou, and Lanhao Zhao. "Decentralized design of consensus protocols with minimal communication links based on directed spanning tree." In 2023 35th Chinese Control and Decision Conference (CCDC). IEEE, 2023. http://dx.doi.org/10.1109/ccdc58219.2023.10327639.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Chen, Yangzhou, Bing Chen, and Jingyuan Zhan. "Decentralized Consensus Criteria of Linear Multiagent Systems via Directed-Spanning-Tree-Based Linear Transformation." In 2019 Chinese Automation Congress (CAC). IEEE, 2019. http://dx.doi.org/10.1109/cac48633.2019.8997344.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Zeng, Zhiwen, Xiangke Wang, and Zhiqiang Zheng. "The model reduction of multi-agent system depended on the spanning tree of directed graph." In 2015 IEEE International Conference on Information and Automation (ICIA). IEEE, 2015. http://dx.doi.org/10.1109/icinfa.2015.7279483.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Zhou, Jiajia, Dingqi Ye, Simon X. Yang, and Xiangling Liu. "Optimal design of consensus for autonomous underwater vehicles with damping term using a directed spanning tree." In OCEANS 2016 - Shanghai. IEEE, 2016. http://dx.doi.org/10.1109/oceansap.2016.7485504.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Directed spanning tree"

1

Mercer-Blackman, Valerie, and Shiela Camingue-Romance. The Impact of United States Tax Policies on Sectoral Foreign Direct Investment to Asia. Asian Development Bank, 2020. http://dx.doi.org/10.22617/wps200388-2.

Full text
Abstract:
Using panel data at the country and sector level spanning almost 15 years, this paper shows that the corporate income tax rate does not affect the United States’ inward foreign direct investment once market size, costs, openness, and the business environment, are taken into account. This is true for United States foreign direct investment bound to developing Asia and across most sectors.
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!

To the bibliography