Given a simple graph G with n vertices, m edges and k connected components. The spanning forest problem is to find a spanning tree for each connected component of G. This problem has applications to the electrical pow...Given a simple graph G with n vertices, m edges and k connected components. The spanning forest problem is to find a spanning tree for each connected component of G. This problem has applications to the electrical power demand problem, computer network design, circuit analysis, etc. In this paper, we present an?time parallel algorithm with processors for constructing a spanning forest on proper circle graph G on EREW PRAM.展开更多
Given a simple graph G with n vertices and m edges, the spanning tree problem is to find a spanning tree for a given graph G. This problem has many applications, such as electric power systems, computer network design...Given a simple graph G with n vertices and m edges, the spanning tree problem is to find a spanning tree for a given graph G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. For a simple graph, the spanning tree problem can be solved in O(log n) time with O(m+n) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs O(log n) time with O(n/log n) processors on the EREW PRAM for constructing on proper circle trapezoid graphs.展开更多
This paper investigates the formation control of a class of multi-agent systems moving on a circle, whose topology is a cyclic graph, and presents several new results for the following two cases: Case I, the agents wi...This paper investigates the formation control of a class of multi-agent systems moving on a circle, whose topology is a cyclic graph, and presents several new results for the following two cases: Case I, the agents with single-integrator kinematics,and Case II, the agents with double-integrator kinematics. Firstly,for Case I, two control protocols are proposed under which the multiagent systems keep a uniformly-spaced formation. Secondly,we study Case II, and a control protocol is designed for this case, then the stability of the formation is proved. Finally, three simulations are studied by using our presented results. The study of illustrative examples with simulations shows that our results as well as designed control protocols work very well in studying the formation control of this class of multi-agent systems.展开更多
文摘Given a simple graph G with n vertices, m edges and k connected components. The spanning forest problem is to find a spanning tree for each connected component of G. This problem has applications to the electrical power demand problem, computer network design, circuit analysis, etc. In this paper, we present an?time parallel algorithm with processors for constructing a spanning forest on proper circle graph G on EREW PRAM.
文摘Given a simple graph G with n vertices and m edges, the spanning tree problem is to find a spanning tree for a given graph G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. For a simple graph, the spanning tree problem can be solved in O(log n) time with O(m+n) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs O(log n) time with O(n/log n) processors on the EREW PRAM for constructing on proper circle trapezoid graphs.
基金supported by the National Natural Science Foundation of China(G61374065,61373081,61303007,61401260,61503225,61572298)the Research Fund for the Taishan Scholar Project of Shandong Province of Chinathe Natural Science Foundation of Shandong Province(ZR2015FQ003)
文摘This paper investigates the formation control of a class of multi-agent systems moving on a circle, whose topology is a cyclic graph, and presents several new results for the following two cases: Case I, the agents with single-integrator kinematics,and Case II, the agents with double-integrator kinematics. Firstly,for Case I, two control protocols are proposed under which the multiagent systems keep a uniformly-spaced formation. Secondly,we study Case II, and a control protocol is designed for this case, then the stability of the formation is proved. Finally, three simulations are studied by using our presented results. The study of illustrative examples with simulations shows that our results as well as designed control protocols work very well in studying the formation control of this class of multi-agent systems.
