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.展开更多
First,the state space tree method for finding communication network overall re-liability is presented.It directly generates one disjoint tree multilevel polynomial of a networkgraph.Its advantages are smaller computat...First,the state space tree method for finding communication network overall re-liability is presented.It directly generates one disjoint tree multilevel polynomial of a networkgraph.Its advantages are smaller computational effort(its computing time complexity is O(en_l),where e is the number of edges and n_l is the number of leaves)and shorter resulting expression.Second,based on it an exact decomposition algorithm for finding communication network overallreliability is presented by applying the hypergraph theory.If we use it to carry out the m-timedecomposition of a network graph,the communication network scale which can be analyzed by acomputer can be extended to m-fold.展开更多
基于Petersen图，提出了Binary Tree Petersen的网络结构，并对其特性进行了研究，证明了Binary Tree Petersen网络具有正则性以及良好的可扩展性，同时还具有比RP（k）、2-DToms更短的直径和良好的并行能力．另外，还基于Binary Tree P...基于Petersen图，提出了Binary Tree Petersen的网络结构，并对其特性进行了研究，证明了Binary Tree Petersen网络具有正则性以及良好的可扩展性，同时还具有比RP（k）、2-DToms更短的直径和良好的并行能力．另外，还基于Binary Tree Petersen网络分别给出了其上的单播和广播路由算法，证明了通信效率都为2j＋4．展开更多
Fault diagnostics is important for safe operation of nuclear power plants(NPPs). In recent years, data-driven approaches have been proposed and implemented to tackle the problem, e.g., neural networks, fuzzy and neuro...Fault diagnostics is important for safe operation of nuclear power plants(NPPs). In recent years, data-driven approaches have been proposed and implemented to tackle the problem, e.g., neural networks, fuzzy and neurofuzzy approaches, support vector machine, K-nearest neighbor classifiers and inference methodologies. Among these methods, dynamic uncertain causality graph(DUCG)has been proved effective in many practical cases. However, the causal graph construction behind the DUCG is complicate and, in many cases, results redundant on the symptoms needed to correctly classify the fault. In this paper, we propose a method to simplify causal graph construction in an automatic way. The method consists in transforming the expert knowledge-based DCUG into a fuzzy decision tree(FDT) by extracting from the DUCG a fuzzy rule base that resumes the used symptoms at the basis of the FDT. Genetic algorithm(GA) is, then, used for the optimization of the FDT, by performing a wrapper search around the FDT: the set of symptoms selected during the iterative search are taken as the best set of symptoms for the diagnosis of the faults that can occur in the system. The effectiveness of the approach is shown with respect to a DUCG model initially built to diagnose 23 faults originally using 262 symptoms of Unit-1 in the Ningde NPP of the China Guangdong Nuclear Power Corporation. The results show that the FDT, with GA-optimized symptoms and diagnosis strategy, can drive the construction of DUCG and lower the computational burden without loss of accuracy in diagnosis.展开更多
Disassembly sequence planning （DSP） plays a significant role in maintenance planning of the aircraft. It is used during the design stage for the analysis of maintainability of the aircraft. To solve product disassem...Disassembly sequence planning （DSP） plays a significant role in maintenance planning of the aircraft. It is used during the design stage for the analysis of maintainability of the aircraft. To solve product disassembly sequence planning problems efficiently, a product disassembly hybrid graph model, which describes the connection, non-connection and precedence relationships between the product parts, is established based on the characteristic of disassembly. Farther, the optimization model is provided to optimize disassembly sequence. And the solution methodology based on the genetic/simulated annealing algorithm with binaxy-tree algorithm is given. Finally, an example is analyzed in detail, and the result shows that the model is correct and efficient.展开更多
This paper is motivated by the concept of the signed k-domination problem and dedicated to the complexity of the problem on graphs. For any fixed nonnegative integer k, we show that the signed k-domination problem is ...This paper is motivated by the concept of the signed k-domination problem and dedicated to the complexity of the problem on graphs. For any fixed nonnegative integer k, we show that the signed k-domination problem is NP-complete for doubly chordal graphs. For strongly chordal graphs and distance-hereditary graphs, we show that the signed k-domination problem can be solved in polynomial time. We also show that the problem is linear-time solvable for trees, interval graphs, and chordal comparability graphs.展开更多
In this paper, we propose an efficient parallel algorithm for generating k spanning trees of a connected, weighted and undirected graph Q(V,E,W) in the order of increasingweight. It runs in O(Tmst(n)+klogn) time with...In this paper, we propose an efficient parallel algorithm for generating k spanning trees of a connected, weighted and undirected graph Q(V,E,W) in the order of increasingweight. It runs in O(Tmst(n)+klogn) time with O(n2/ logn) processors on a CREW PRAM,where n=|V|, m=|E| and Tmst(n), O(log n)＜Tmst(n)＜O(log2 n) is the run time of the fastest parallel algorithm for finding a minimum spanning tree (MST) of G on a CREW PRAM. SinceTmst(n)=O(log2 n) for the time being, our algorithm is of the same time bound with Tmst(n)when k＜O(log n).展开更多
文摘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.
文摘First,the state space tree method for finding communication network overall re-liability is presented.It directly generates one disjoint tree multilevel polynomial of a networkgraph.Its advantages are smaller computational effort(its computing time complexity is O(en_l),where e is the number of edges and n_l is the number of leaves)and shorter resulting expression.Second,based on it an exact decomposition algorithm for finding communication network overallreliability is presented by applying the hypergraph theory.If we use it to carry out the m-timedecomposition of a network graph,the communication network scale which can be analyzed by acomputer can be extended to m-fold.
文摘基于Petersen图，提出了Binary Tree Petersen的网络结构，并对其特性进行了研究，证明了Binary Tree Petersen网络具有正则性以及良好的可扩展性，同时还具有比RP（k）、2-DToms更短的直径和良好的并行能力．另外，还基于Binary Tree Petersen网络分别给出了其上的单播和广播路由算法，证明了通信效率都为2j＋4．
文摘Fault diagnostics is important for safe operation of nuclear power plants(NPPs). In recent years, data-driven approaches have been proposed and implemented to tackle the problem, e.g., neural networks, fuzzy and neurofuzzy approaches, support vector machine, K-nearest neighbor classifiers and inference methodologies. Among these methods, dynamic uncertain causality graph(DUCG)has been proved effective in many practical cases. However, the causal graph construction behind the DUCG is complicate and, in many cases, results redundant on the symptoms needed to correctly classify the fault. In this paper, we propose a method to simplify causal graph construction in an automatic way. The method consists in transforming the expert knowledge-based DCUG into a fuzzy decision tree(FDT) by extracting from the DUCG a fuzzy rule base that resumes the used symptoms at the basis of the FDT. Genetic algorithm(GA) is, then, used for the optimization of the FDT, by performing a wrapper search around the FDT: the set of symptoms selected during the iterative search are taken as the best set of symptoms for the diagnosis of the faults that can occur in the system. The effectiveness of the approach is shown with respect to a DUCG model initially built to diagnose 23 faults originally using 262 symptoms of Unit-1 in the Ningde NPP of the China Guangdong Nuclear Power Corporation. The results show that the FDT, with GA-optimized symptoms and diagnosis strategy, can drive the construction of DUCG and lower the computational burden without loss of accuracy in diagnosis.
基金supported by the National High Technology Research and Development Program of China(2006AA04Z427).
文摘Disassembly sequence planning （DSP） plays a significant role in maintenance planning of the aircraft. It is used during the design stage for the analysis of maintainability of the aircraft. To solve product disassembly sequence planning problems efficiently, a product disassembly hybrid graph model, which describes the connection, non-connection and precedence relationships between the product parts, is established based on the characteristic of disassembly. Farther, the optimization model is provided to optimize disassembly sequence. And the solution methodology based on the genetic/simulated annealing algorithm with binaxy-tree algorithm is given. Finally, an example is analyzed in detail, and the result shows that the model is correct and efficient.
文摘This paper is motivated by the concept of the signed k-domination problem and dedicated to the complexity of the problem on graphs. For any fixed nonnegative integer k, we show that the signed k-domination problem is NP-complete for doubly chordal graphs. For strongly chordal graphs and distance-hereditary graphs, we show that the signed k-domination problem can be solved in polynomial time. We also show that the problem is linear-time solvable for trees, interval graphs, and chordal comparability graphs.
文摘In this paper, we propose an efficient parallel algorithm for generating k spanning trees of a connected, weighted and undirected graph Q(V,E,W) in the order of increasingweight. It runs in O(Tmst(n)+klogn) time with O(n2/ logn) processors on a CREW PRAM,where n=|V|, m=|E| and Tmst(n), O(log n)＜Tmst(n)＜O(log2 n) is the run time of the fastest parallel algorithm for finding a minimum spanning tree (MST) of G on a CREW PRAM. SinceTmst(n)=O(log2 n) for the time being, our algorithm is of the same time bound with Tmst(n)when k＜O(log n).
