Log in

Relevant bibliographies by topics / Directed spanning tree / Journal articles

To see the other types of publications on this topic, follow the link: Directed spanning tree.

Journal articles on the topic 'Directed spanning tree'

Author: Grafiati

Published: 3 June 2025

Last updated: 6 July 2025

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

Select a source type:

Consult the top 50 journal articles for your research 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.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

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

11

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

Full text

Abstract:

In Bhatt and Roy's minimal directed spanning tree construction fornrandom 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 largen) 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

12

Mayliana, Mayliana. "Optimasi Jaringan dengan Spanning Tree untuk Congestion Management." ComTech: Computer, Mathematics and Engineering Applications 5, no. 1 (2014): 53. http://dx.doi.org/10.21512/comtech.v5i1.2582.

Full text

Abstract:

A proper network optimization is needed to deal with problems on the network and to minimize latency in the data flow in a dense network. The data stream is directed into the right channels so that the optimal network speed and latency can be minimized. Spanning tree is one of the algorithms that can be used. The purpose of the Spanning tree is to prevent and reduce the loops in the network by negotiating free path and as well as to increase network uptime through redundancy (back-up). To comprehend spanning tree, the first important thing to know is how bridges and switches perform their functions. The more switches used, the use of the spanning tree becomes more important. With the spanning tree protocol, a broadcast storm can be prevented that can achieved network optimization.

APA, Harvard, Vancouver, ISO, and other styles

13

Mary, Francis Remigius Perpetua, Swaminathan Mohanaselvi, and Said Broumi. "A solution approach to minimum spanning tree problem under fermatean fuzzy environment." Bulletin of Electrical Engineering and Informatics 12, no. 3 (2023): 1738–46. http://dx.doi.org/10.11591/eei.v12i3.4794.

Full text

Abstract:

In classical graph theory, the minimal spanning tree (MST) is a subgraph with no cycles that connects each vertex with minimum edge weights. Calculating minimum spanning tree of a graph has always been a common problem throughout ages. Fuzzy minimum spanning tree (FMST) is able to handle uncertainty existing in edge weights for a fuzzy graph which occurs in real world situations. In this article, we have studied the MST problem of a directed and undirected fuzzy graph whose edge weights are represented by fermatean fuzzy numbers (FFN). We focus on determining an algorithmic approach for solving fermatean fuzzy minimum spanning tree (FFMST) using the modified Prim’s algorithm for an undirected graph and modified optimum branching algorithm for a directed graph under FFN environment. Since the proposed algorithm includes FFN ranking and arithmetic operations, we use FFNs improved scoring function to compare the weights of the edges of the graph. With the help of numerical examples, the solution technique for the proposed FFMST model is described.

APA, Harvard, Vancouver, ISO, and other styles

14

Harrigan, Martin, and Patrick Healy. "Using a Significant Spanning Tree to Draw a Directed Graph." Journal of Graph Algorithms and Applications 12, no. 3 (2008): 293–317. http://dx.doi.org/10.7155/jgaa.00168.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Coupier, David, and Viet Chi Tran. "The 2D-directed spanning forest is almost surely a tree." Random Structures & Algorithms 42, no. 1 (2012): 59–72. http://dx.doi.org/10.1002/rsa.20400.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Francis, Remigius Perpetua Mary, Mohanaselvi Swaminathan, and Broumi Said. "A solution approach to minimum spanning tree problem under fermatean fuzzy environment." Bulletin of Electrical Engineering and Informatics 12, no. 3 (2023): 1738~1746. https://doi.org/10.11591/eei.v12i3.4794.

Full text

Abstract:

In classical graph theory, the minimal spanning tree (MST) is a subgraph with no cycles that connects each vertex with minimum edge weights. Calculating minimum spanning tree of a graph has always been a common problem throughout ages. Fuzzy minimum spanning tree (FMST) is able to handle uncertainty existing in edge weights for a fuzzy graph which occurs in real world situations. In this article, we have studied the MST problem of a directed and undirected fuzzy graph whose edge weights are represented by fermatean fuzzy numbers (FFN). We focus on determining an algorithmic approach for solving fermatean fuzzy minimum spanning tree (FFMST) using the modified Prim’s algorithm for an undirected graph and modified optimum branching algorithm for a directed graph under FFN environment. Since the proposed algorithm includes FFN ranking and arithmetic operations, we use FFNs improved scoring function to compare the weights of the edges of the graph. With the help of numerical examples, the solution technique for the proposed FFMST model is described.

APA, Harvard, Vancouver, ISO, and other styles

17

Wang, Wenshuai, Juling Wang, Huaizhu Wang, and Yuanshi Zheng. "Consensus of Heterogeneous Multiagent Systems with Switching Dynamics." Mathematical Problems in Engineering 2018 (November 5, 2018): 1–9. http://dx.doi.org/10.1155/2018/5179470.

Full text

Abstract:

Heterogeneity is an important feature of multiagent systems. This paper addresses the consensus problem of heterogeneous multiagent systems composed of first-integrator and double-integrator agents. The dynamics of each agent switches between continuous-time and discrete-time dynamics. By using the graph theory and nonnegative matrix theory, we derive that the system can achieve consensus if and only if the fixed interaction topology has a directed spanning tree. For switching topologies, we get that the system can reach consensus if each interaction topology has a directed spanning tree. Simulation examples are provided to demonstrate the effectiveness of our theoretical results.

APA, Harvard, Vancouver, ISO, and other styles

18

Yue, Dongdong, Simone Baldi, Jinde Cao, Qi Li, and Bart De Schutter. "A Directed Spanning Tree Adaptive Control Solution to Time-Varying Formations." IEEE Transactions on Control of Network Systems 8, no. 2 (2021): 690–701. http://dx.doi.org/10.1109/tcns.2021.3050332.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Bai, Z. D., Sungchul Lee, and Mathew D. Penrose. "Rooted edges of a minimal directed spanning tree on random points." Advances in Applied Probability 38, no. 1 (2006): 1–30. http://dx.doi.org/10.1239/aap/1143936137.

Full text

Abstract:

For n independent, identically distributed uniform points in [0, 1]d, d ≥ 2, let Ln be the total distance from the origin to all the minimal points under the coordinatewise partial order (this is also the total length of the rooted edges of a minimal directed spanning tree on the given random points). For d ≥ 3, we establish the asymptotics of the mean and the variance of Ln, and show that Ln satisfies a central limit theorem, unlike in the case d = 2.

APA, Harvard, Vancouver, ISO, and other styles

20

Penrose, Mathew D., and Andrew R. Wade. "On the total length of the random minimal directed spanning tree." Advances in Applied Probability 38, no. 2 (2006): 336–72. http://dx.doi.org/10.1239/aap/1151337075.

Full text

Abstract:

In Bhatt and Roy's minimal directed spanning tree construction for a random, partially ordered set of points in the unit square, all edges must respect the ‘coordinatewise’ partial order and there must be a directed path from each vertex to a minimal element. We study the asymptotic behaviour of the total length of this graph with power-weighted edges. The limiting distribution is given by the sum of a normal component away from the boundary plus a contribution introduced by the boundary effects, which can be characterized by a fixed-point equation, and is reminiscent of limits arising in the probabilistic analysis of certain algorithms. As the exponent of the power weighting increases, the distribution undergoes a phase transition from the normal contribution being dominant to the boundary effects being dominant. In the critical case in which the weight is simple Euclidean length, both effects contribute significantly to the limit law.

APA, Harvard, Vancouver, ISO, and other styles

21

Bai, Z. D., Sungchul Lee, and Mathew D. Penrose. "Rooted edges of a minimal directed spanning tree on random points." Advances in Applied Probability 38, no. 01 (2006): 1–30. http://dx.doi.org/10.1017/s000186780000077x.

Full text

Abstract:

For n independent, identically distributed uniform points in [0, 1] d , d ≥ 2, let L n be the total distance from the origin to all the minimal points under the coordinatewise partial order (this is also the total length of the rooted edges of a minimal directed spanning tree on the given random points). For d ≥ 3, we establish the asymptotics of the mean and the variance of L n , and show that L n satisfies a central limit theorem, unlike in the case d = 2.

APA, Harvard, Vancouver, ISO, and other styles

22

Penrose, Mathew D., and Andrew R. Wade. "On the total length of the random minimal directed spanning tree." Advances in Applied Probability 38, no. 02 (2006): 336–72. http://dx.doi.org/10.1017/s0001867800001002.

Full text

Abstract:

In Bhatt and Roy's minimal directed spanning tree construction for a random, partially ordered set of points in the unit square, all edges must respect the ‘coordinatewise’ partial order and there must be a directed path from each vertex to a minimal element. We study the asymptotic behaviour of the total length of this graph with power-weighted edges. The limiting distribution is given by the sum of a normal component away from the boundary plus a contribution introduced by the boundary effects, which can be characterized by a fixed-point equation, and is reminiscent of limits arising in the probabilistic analysis of certain algorithms. As the exponent of the power weighting increases, the distribution undergoes a phase transition from the normal contribution being dominant to the boundary effects being dominant. In the critical case in which the weight is simple Euclidean length, both effects contribute significantly to the limit law.

APA, Harvard, Vancouver, ISO, and other styles

23

Das, Priyanka, Asit Kumar Das, and Janmenjoy Nayak. "Feature selection generating directed rough-spanning tree for crime pattern analysis." Neural Computing and Applications 32, no. 12 (2018): 7623–39. http://dx.doi.org/10.1007/s00521-018-3880-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Zhao, Wenbiao, Runxin Li, and Zhenhong Shang. "Multilabel Classifier Chains Algorithm Based on Maximum Spanning Tree and Directed Acyclic Graph." International Journal of Information Technologies and Systems Approach 16, no. 3 (2023): 1–21. http://dx.doi.org/10.4018/ijitsa.324066.

Full text

Abstract:

The classifier chains algorithm is aimed at solving the multilabel classification problem by composing the labels into a randomized label order. The classification effect of this algorithm depends heavily on whether the label order is optimal. To obtain a better label ordering, the authors propose a multilabel classifier chains algorithm based on a maximum spanning tree and a directed acyclic graph. The algorithm first uses Pearson's correlation coefficient to calculate the correlation between labels and constructs the maximum spanning tree of labels, then calculates the mutual decision difficulty between labels to transform the maximum spanning tree into a directed acyclic graph, and it uses topological ranking to output the optimized label ordering. Finally, the authors use the classifier chains algorithm to train and predict against this label ordering. Experimental comparisons were conducted between the proposed algorithm and other related algorithms on seven datasets, and the proposed algorithm ranked first and second in six evaluation metrics, accounting for 76.2% and 16.7%, respectively. The experimental results demonstrated the effectiveness of the proposed algorithm and affirmed its contribution in exploring and utilizing label-related information.

APA, Harvard, Vancouver, ISO, and other styles

25

Yu, Zhiyong, Da Huang, Haijun Jiang, Cheng Hu, and Wenwu Yu. "Distributed Consensus for Multiagent Systems via Directed Spanning Tree Based Adaptive Control." SIAM Journal on Control and Optimization 56, no. 3 (2018): 2189–217. http://dx.doi.org/10.1137/16m1088685.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Gouveia, Luis. "A comparison of directed formulations for the capacitated minimal spanning tree problem." Telecommunication Systems 1, no. 1 (1993): 51–76. http://dx.doi.org/10.1007/bf02136155.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Gioan, Emeric, and Michel Las Vergnas. "Computing the fully optimal spanning tree of an ordered bipolar directed graph." Discrete Mathematics 347, no. 5 (2024): 113895. http://dx.doi.org/10.1016/j.disc.2024.113895.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Tan, Yanying, Liang Xue, Yanning Zhang, and Xiaoping Zhu. "Control Strategies for Multi-UAV Simultaneous Arrival under Communication Topology Changing." Xibei Gongye Daxue Xuebao/Journal of Northwestern Polytechnical University 36, no. 3 (2018): 565–70. http://dx.doi.org/10.1051/jnwpu/20183630565.

Full text

Abstract:

Aimed at changing in communication topology due to partial link/node failure in the battlefield, and for satisfying the weakest connectivity criteria of consensus algorithm, the strategy of judging in real time whether the communication topology among UAVs has a directed spanning tree or sub-tree and the strategy of acquiring the expected minimum partial link change suggestion for the topology containing a directed spanning tree again are designed. Based on the above strategies and selecting ETA (Estimated Time of Arrival) as coordinated variable, the consensus algorithm ensures that after some time all the members or part members of the UAVs arrive simultaneously. The strategy is put forword which the UAVS are controlled arriving simultaneously on the planed virtual sub-goal waypoints one by one along the flight path. Through the strategy, the UAVs fly together soon and arrive simultaneously at last. It is helpful to improve the survival rate of UAVs and preserve the communication connectivity of UAVs which is usually distance-dependent. The simulation results show that the above strategies are effective.

APA, Harvard, Vancouver, ISO, and other styles

29

Bonsma, Paul, and Frederic Dorn. "Tight bounds and a fast FPT algorithm for directed Max-Leaf Spanning Tree." ACM Transactions on Algorithms 7, no. 4 (2011): 1–19. http://dx.doi.org/10.1145/2000807.2000812.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Binkele-Raible, Daniel, and Henning Fernau. "An exact exponential-time algorithm for the Directed Maximum Leaf Spanning Tree problem." Journal of Discrete Algorithms 15 (August 2012): 43–55. http://dx.doi.org/10.1016/j.jda.2012.03.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Lin, Ching-Chi, Gerard J. Chang, and Gen-Huey Chen. "The degree-preserving spanning tree problem in strongly chordal and directed path graphs." Networks 56, no. 3 (2009): 183–87. http://dx.doi.org/10.1002/net.20359.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Yu, Zhiyong, Haijun Jiang, Da Huang, and Cheng Hu. "Directed spanning tree-based adaptive protocols for second-order consensus of multiagent systems." International Journal of Robust and Nonlinear Control 28, no. 6 (2017): 2172–90. http://dx.doi.org/10.1002/rnc.4009.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

WANG, QINGLING, and YUANDA WANG. "Exponential Consensus in Directed Networks of Multi-Agents with Saturated Protocols." Journal of Interconnection Networks 16, no. 02 (2016): 1650003. http://dx.doi.org/10.1142/s0219265916500031.

Full text

Abstract:

This paper addresses the exponential consensus problem of single-integrator agents with saturated protocols on directed graphs. By employing an integral Lyapunov function, the exponential consensus problem of single-integrator agents is solved under the directed graph with strongly connected or a spanning tree. The main contribution is that under the directed graph, some conditions for exponential consensus with saturated protocols are first obtained. Finally, two examples are used to illustrate the effectiveness of the theoretical results.

APA, Harvard, Vancouver, ISO, and other styles

34

Yu, Zhiyong, Haijun Jiang, Da Huang, and Cheng Hu. "Consensus of nonlinear multi-agent systems with directed switching graphs: A directed spanning tree based error system approach." Nonlinear Analysis: Hybrid Systems 28 (May 2018): 123–40. http://dx.doi.org/10.1016/j.nahs.2017.12.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Chwatal, Andreas M., and Günther R. Raidl. "Solving the Minimum Label Spanning Tree Problem by Mathematical Programming Techniques." Advances in Operations Research 2011 (2011): 1–38. http://dx.doi.org/10.1155/2011/143732.

Full text

Abstract:

We present exact mixed integer programming approaches including branch-and-cut and branch-and-cut-and-price for the minimum label spanning tree problem as well as a variant of it having multiple labels assigned to each edge. We compare formulations based on network flows and directed connectivity cuts. Further, we show how to use odd-hole inequalities and additional inequalities to strengthen the formulation. Label variables can be added dynamically to the model in the pricing step. Primal heuristics are incorporated into the framework to speed up the overall solution process. After a polyhedral comparison of the involved formulations, comprehensive computational experiments are presented in order to compare and evaluate the underlying formulations and the particular algorithmic building blocks of the overall branch-and-cut- (and-price) framework.

APA, Harvard, Vancouver, ISO, and other styles

36

Yan, Zheping, Di Wu, Wei Zhang, and Yibo Liu. "Consensus of Multiagent Systems with Packet Losses and Communication Delays Using a Novel Control Protocol." Abstract and Applied Analysis 2014 (2014): 1–13. http://dx.doi.org/10.1155/2014/159609.

Full text

Abstract:

This paper studies the consensus problem of multiagent system with packet losses and communication delays under directed communication channels. Different from previous research results, a novel control protocol is proposed depending only on periodic sampling and transmitting data in order to be convenient for practical implementation. Due to the randomicity of transmission delays and packet losses, each agent updates its input value asynchronously at discrete time instants with synchronized time stamped information and evolves in continuous time. Consensus conditions for multiagent system consists of three typical dynamics including single integrator, double integrator, and high-order integrator that are all discussed in this paper. It is proved that, for single integrator agents and double integrator systems with only communication delays, consensusability can be ensured through stochastic matrix theory if the designed communication topology contains a directed spanning tree. While, for double integrator agents and high-order integrator agents with packet losses and communication delays, the interval system theory is introduced to prove the consensus of multiagent system under the condition that the designed communication topology is a directed spanning tree. Finally, simulations are carried out to validate the effectiveness of the proposed solutions.

APA, Harvard, Vancouver, ISO, and other styles

37

Dai, Hao, Jinping Jia, Li Yan, Fakui Wang, and Weisheng Chen. "Event-triggered exponential synchronization of complex dynamical networks with cooperatively directed spanning tree topology." Neurocomputing 330 (February 2019): 355–68. http://dx.doi.org/10.1016/j.neucom.2018.11.013.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Sajwan, N., I. Sharma, A. Kumar, and L. K. Balyan. "Performance of Multiplierless FIR Filter Based on Directed Minimal Spanning Tree: A Comparative Study." Circuits, Systems, and Signal Processing 39, no. 11 (2020): 5776–800. http://dx.doi.org/10.1007/s00034-020-01433-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Lu, Xin Biao, and Yue Yuan. "The Effect of Battery Recharge Spat for Electric Vehicle Car on the Grid." Applied Mechanics and Materials 448-453 (October 2013): 3177–80. http://dx.doi.org/10.4028/www.scientific.net/amm.448-453.3177.

Full text

Abstract:

Adaptive strategy of directed dynamical networks with switching topologies is proposed to eleminate the harmonic superposition, which is brought by the use of the electric vehicle chargeing spats. It is found that if there exists a directed spanning tree in the fixed time-average of network topology and the time-average is achieved sufficiently fast, then harmonic superposition of the network will be suppressed effectienly. A sufficient condition is derived. Several numerical simulations show the effectiveness of the adaptive strategy.

APA, Harvard, Vancouver, ISO, and other styles

40

Zhu, Xu, Jian Guo Yan, and Yao Hong Qu. "Consensus Problems for High-Order Multi-Agent Systems." Advanced Materials Research 403-408 (November 2011): 2736–39. http://dx.doi.org/10.4028/www.scientific.net/amr.403-408.2736.

Full text

Abstract:

An information consensus algorithm for high-order multi-agent systems is proposed based on algebraic graph theory. Sufficient and necessary conditions are given for each information to converge to common values. The network topology of multi-agent systems has a directed spanning tree and each weight of different derivatives is positive, then consensus is achieved.

APA, Harvard, Vancouver, ISO, and other styles

41

Cohen, Joel E. "Connectivity of finite anisotropic random graphs and directed graphs." Mathematical Proceedings of the Cambridge Philosophical Society 99, no. 2 (1986): 315–30. http://dx.doi.org/10.1017/s0305004100064239.

Full text

Abstract:

AbstractFor graphs on a finite set of vertices with arbitrary probabilities of independently occurring edges, the reliability is defined as the probability that the graph is connected, and the redundancy as the expected number of spanning trees of the graph. Analogous measures of connectivity are defined for random finite directed graphs with arbitrary probabilities of independently occurring directed edges. Recursive formulas for computing the reliability are known. Determinantal formulas, based on matrix-tree theorems, for computing the redundancy are given here. Among random graphs with a given sum of edge probabilities, the more evenly the probabilities are distributed over potential edges, the larger the redundancy. This inequality, proved using the theory of majorization, in combination with examples shows unexpectedly that conflicts between reliability and redundancy can arise in the design of communication networks modelled by such random graphs. The significance of these calculations for the command and control of nuclear forces is sketched.

APA, Harvard, Vancouver, ISO, and other styles

42

Yang, Chunde, Wenjing Li, and Wei Zhu. "Consensus Analysis of Fractional-Order Multiagent Systems with Double-Integrator." Discrete Dynamics in Nature and Society 2017 (2017): 1–8. http://dx.doi.org/10.1155/2017/9256532.

Full text

Abstract:

In nature, many phenomena can be explained by coordinated behavior of agents with fractional-order dynamics. In this paper, the consensus problem of fractional-order multiagent systems with double-integrator is studied, where the fractional-order satisfies0<α<2. Based on the fractional-order stability theory, Mittag-Leffler function, and Laplace transform, a necessary and sufficient condition is obtained under the assumption that the directed graph for the communication network contains a directed spanning tree. Finally, an example with simulation is presented to illustrate the theoretical results.

APA, Harvard, Vancouver, ISO, and other styles

43

Restrepo, Esteban, Antonio Loría, Ioannis Sarras, and Julien Marzat. "Robust Consensus and Connectivity-maintenance under Edge-agreement-based Protocols for Directed Spanning Tree Graphs." IFAC-PapersOnLine 53, no. 2 (2020): 2988–93. http://dx.doi.org/10.1016/j.ifacol.2020.12.978.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Subbarao, K., and M. Ahmed. "Target tracking using multiple unmanned aerial vehicles: Graph theoretic nonlinear control approach." Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering 231, no. 3 (2016): 570–86. http://dx.doi.org/10.1177/0954410016641321.

Full text

Abstract:

This paper develops a cooperative controller for multiple Unmanned Aerial Vehicles (UAVs) with application to target tracking. The cooperation between the UAVs is established based on an algebraic graph connection and the target information is provided externally by pinning it into a subset of the network. A backstepping-like technique is employed to design a consensus-based controller for each UAV in order to achieve target tracking in 3-D. The proposed controller computes commanded signals for the speed, flight path angle, and heading angle to track the target. The paper considers both the cases of fixed and dynamically changing communication topologies. It is shown that target tracking is achieved for fixed connection topology, if the graph has a directed spanning tree; and for the dynamically changing topology, if the union of the graphs over finite time intervals has a directed spanning tree. The system’s stability is shown using a Lyapunov function-based approach for these cases. All tracking errors are shown to be bounded as long as the target states and its derivatives up to second order are bounded. Detailed numerical simulations further illustrate the controller performance.

APA, Harvard, Vancouver, ISO, and other styles

45

Min, Seunghwan, Sung Gwan Park, Kunsoo Park, Dora Giammarresi, Giuseppe F. Italiano, and Wook-Shin Han. "Symmetric continuous subgraph matching with bidirectional dynamic programming." Proceedings of the VLDB Endowment 14, no. 8 (2021): 1298–310. http://dx.doi.org/10.14778/3457390.3457395.

Full text

Abstract:

In many real datasets such as social media streams and cyber data sources, graphs change over time through a graph update stream of edge insertions and deletions. Detecting critical patterns in such dynamic graphs plays an important role in various application domains such as fraud detection, cyber security, and recommendation systems for social networks. Given a dynamic data graph and a query graph, the continuous subgraph matching problem is to find all positive matches for each edge insertion and all negative matches for each edge deletion. The state-of-the-art algorithm TurboFlux uses a spanning tree of a query graph for filtering. However, using the spanning tree may have a low pruning power because it does not take into account all edges of the query graph. In this paper, we present a symmetric and much faster algorithm SymBi which maintains an auxiliary data structure based on a directed acyclic graph instead of a spanning tree, which maintains the intermediate results of bidirectional dynamic programming between the query graph and the dynamic graph. Extensive experiments with real and synthetic datasets show that SymBi outperforms the state-of-the-art algorithm by up to three orders of magnitude in terms of the elapsed time.

APA, Harvard, Vancouver, ISO, and other styles

46

Jiang, Tong Qiang, Jia Wei He, and Yan Ping Gao. "Consensus Problem of Singular Multi-Agent Systems with Continuous-Time and Fixed Topology." Applied Mechanics and Materials 278-280 (January 2013): 1687–91. http://dx.doi.org/10.4028/www.scientific.net/amm.278-280.1687.

Full text

Abstract:

The consensus problems of two situations for singular multi-agent systems with fixed topology are discussed: directed graph without spanning tree and the disconnected undirected graph. A sufficient and necessary condition is obtained by applying the stability theory and the system is reachable asymptotically. But for normal systems, this can’t occur in upper two situations. Finally a simulation example is provided to verify the effectiveness of our theoretical result.

APA, Harvard, Vancouver, ISO, and other styles

47

BIDKHORI, HODA, and SHAUNAK KISHORE. "A Bijective Proof of a Theorem of Knuth." Combinatorics, Probability and Computing 20, no. 1 (2010): 11–25. http://dx.doi.org/10.1017/s0963548310000192.

Full text

Abstract:

The line graph G of a directed graph G has a vertex for every edge of G and an edge for every path of length 2 in G. In 1967, Knuth used the Matrix Tree Theorem to prove a formula for the number of spanning trees of G, and he asked for a bijective proof [6]. In this paper, we give a bijective proof of Knuth's formula. As a result of this proof, we find a bijection between binary de Bruijn sequences of degree n and binary sequences of length 2n−1. Finally, we determine the critical groups of all the Kautz graphs and de Bruijn graphs, generalizing a result of Levine [7].

APA, Harvard, Vancouver, ISO, and other styles

48

Liu, Wei, Shaolei Zhou, Shi Yan, and Gaoyang Yin. "Robust Leaderless Consensus of Uncertain Multiagent Systems with Fast Switching Topologies." Mathematical Problems in Engineering 2015 (2015): 1–6. http://dx.doi.org/10.1155/2015/810950.

Full text

Abstract:

This paper investigates the robust leaderless consensus problem of uncertain multiagent systems with directed fast switching topologies. The topologies are assumed to jointly contain a directed spanning tree. Based on a special property of the graph Laplacian matrix, the consensus problem is converted into a stabilization problem by performing a proper variable transformation. Averaging method is employed for analysis. It is proved that if the topologies switch sufficiently fast and the controllers are properly designed, the robust leaderless consensus can still be achieved even when all the possible topologies are unconnected in the switching time intervals. Finally, a numerical simulation is provided to illustrate the effectiveness of the theoretical results.

APA, Harvard, Vancouver, ISO, and other styles

49

Liu, Wei, Shaolei Zhou, Qingpo Wu, and Gaoyang Yin. "H∞ consensus of multi-agent systems in directed networks with Lipschitz non-linear dynamics." Transactions of the Institute of Measurement and Control 39, no. 12 (2016): 1877–84. http://dx.doi.org/10.1177/0142331216655395.

Full text

Abstract:

This paper studies the H∞ consensus problem of multi-agent systems with Lipschitz non-linearities and external disturbances in a general network. The topology is just required to contain a directed spanning tree. Distributed consensus controllers are constructed based on relative states information of neighbour agents. A novel matrix decomposition based approach is introduced to analyse the H∞ consensus problem, in which the H∞ consensus problem is converted into a H∞ control problem of lower dimension system by performing a proper linear variable transformation. Finally, the effectiveness of the theoretical results is illustrated via a numerical simulation.

APA, Harvard, Vancouver, ISO, and other styles

50

De Haas, Desli, Citra Palembang, and Aziz Rumakefing. "Solution Approach to the Minimum Spanning Tree Problem in Tsukamoto Fuzzy and Fermantean Fuzzy Environments." Digital Zone: Jurnal Teknologi Informasi dan Komunikasi 15, no. 2 (2024): 208–21. https://doi.org/10.31849/digitalzone.v15i2.22826.

Full text

Abstract:

Solving Fuzzy Minimum Spanning Tree (FFMST) and Fuzzy Tsukamoto using modified Prim Algorithm for Undirected Graphs and modified Optimal Branching Algorithm for Directed Graphs in FFN environment. Since the proposed Algorithm includes FFN ranking and Arithmetic Operations, we use the improved FFN scoring function to compare the edge weights of the graphs. With the help of Numerical examples, the solution technique for the proposed FFMST model is explained. It aims to modify the Prims algorithm for oriktade graphing and the optimal result processing algorithm for re-graphing in Fuzzy Fermatean ( FFN )-miljö. They utilize the finite FFN function and the operation of fuzzy function operations to ensure victory in graphing. The fuzzy-inference process is based on the Tsukamoto method and also to get the best result from the existing catch. Numerical examples of presenters to perform the tasks of missing presenters. The results are seen in the effective Prim algorithm modifier lost Fuzzy Fermatean MST -problem for genome oriktade generator generated at minimum cost and fall with local banks. It is an optimal business growth modifier to optimize services for lenders, such as communication between financial consultants and commercial banks. This method will be effective and increase the desired parameters. Tsukamoto Fuzzy -This method includes a fuzzy-inference process to get the best answer in the minimum spanning tree problem. Kantvikter functions based on levels of capability and range functions. Theminimum spanning tree is achieved by the Prims algorithm, which may be performed with fuzzy values first.

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!