基于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．展开更多
Most solutions for detecting buffer overflow are based on source code. But the requirement tor source code is not always practical especially for business software. A new approach was presented to detect statically th...Most solutions for detecting buffer overflow are based on source code. But the requirement tor source code is not always practical especially for business software. A new approach was presented to detect statically the potential buffer overflow vulnerabilities in the binary code of software. The binary code was translated into assembly code without the lose of the information of string operation functions. The feature code abstract graph was constructed to generate more accurate constraint statements, and analyze the assembly code using the method of integer range constraint. After getting the elementary report on suspicious code where buffer overflows possibly happen, the control flow sensitive analysis using program dependence graph was done to decrease the rate of false positive. A prototype was implemented which demonstrates the feasibility and efficiency of the new approach.展开更多
The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decis...The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decision diagram (ADD) or variants thereof provides canonical forms to represent and manipulate Boolean functions and pseudo-Boolean functions efficiently. ADD and OBDD-based symbolic algorithms give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic ADD formulation and algorithm for maximum weighted matching in bipartite graphs. The symbolic algorithm implements the Hungarian algorithm in the context of ADD and OBDD formulation and manipulations. It begins by setting feasible labelings of nodes and then iterates through a sequence of phases. Each phase is divided into two stages. The first stage is building equality bipartite graphs, and the second one is finding maximum cardinality matching in equality bipartite graph. The second stage iterates through the following steps: greedily searching initial matching, building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. The symbolic algorithm does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments indicate that symbolic algorithm is competitive with traditional algorithms.展开更多
Recent years have seen an explosion in graph data from a variety of scientific,social and technological fields.From these fields,emotion recognition is an interesting research area because it finds many applications i...Recent years have seen an explosion in graph data from a variety of scientific,social and technological fields.From these fields,emotion recognition is an interesting research area because it finds many applications in real life such as in effective social robotics to increase the interactivity of the robot with human,driver safety during driving,pain monitoring during surgery etc.A novel facial emotion recognition based on graph mining has been proposed in this paper to make a paradigm shift in the way of representing the face region,where the face region is represented as a graph of nodes and edges and the gSpan frequent sub-graphs mining algorithm is used to find the frequent sub-structures in the graph database of each emotion.To reduce the number of generated sub-graphs,overlap ratio metric is utilized for this purpose.After encoding the final selected sub-graphs,binary classification is then applied to classify the emotion of the queried input facial image using six levels of classification.Binary cat swarm intelligence is applied within each level of classification to select proper sub-graphs that give the highest accuracy in that level.Different experiments have been conducted using Surrey Audio-Visual Expressed Emotion(SAVEE)database and the final system accuracy was 90.00%.The results show significant accuracy improvements(about 2%)by the proposed system in comparison to current published works in SAVEE database.展开更多
The optimal semi-matching problem is one relaxing form of the maximum cardinality matching problems in bipartite graphs, and finds its applications in load balancing. Ordered binary decision diagram (OBDD) is a canoni...The optimal semi-matching problem is one relaxing form of the maximum cardinality matching problems in bipartite graphs, and finds its applications in load balancing. Ordered binary decision diagram (OBDD) is a canonical form to represent and manipulate Boolean functions efficiently. OBDD-based symbolic algorithms appear to give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic OBDD formulation and algorithm for the optimal semi-matching problem in bipartite graphs. The symbolic algorithm is initialized by heuristic searching initial matching and then iterates through generating residual network, building layered network, backward traversing node-disjoint augmenting paths, and updating semi-matching. It does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Our simulations show that symbolic algorithm has better performance, especially on dense and large graphs.展开更多
In this paper, we deduce Wiener number of some connected subgraphs in tilings (4, 4, 4, 4) and (4, 6, 12), which are in Archimedean tilings. And compute their average distance.
In this paper,we consider the NP-hard problem of finding the minimum dominant resolving set of graphs.A vertex set B of a connected graph G resolves G if every vertex of G is uniquely identified by its vector of dista...In this paper,we consider the NP-hard problem of finding the minimum dominant resolving set of graphs.A vertex set B of a connected graph G resolves G if every vertex of G is uniquely identified by its vector of distances to the vertices in B.A resolving set is dominating if every vertex of G that does not belong to B is a neighbor to some vertices in B.The dominant metric dimension of G is the cardinality number of the minimum dominant resolving set.The dominant metric dimension is computed by a binary version of the Archimedes optimization algorithm(BAOA).The objects of BAOA are binary encoded and used to represent which one of the vertices of the graph belongs to the dominant resolving set.The feasibility is enforced by repairing objects such that an additional vertex generated from vertices of G is added to B and this repairing process is iterated until B becomes the dominant resolving set.This is the first attempt to determine the dominant metric dimension problem heuristically.The proposed BAOA is compared to binary whale optimization(BWOA)and binary particle optimization(BPSO)algorithms.Computational results confirm the superiority of the BAOA for computing the dominant metric dimension.展开更多
In this paper we discuss the convergence of the directed graph-algorithm for solving a kind of optimization problems where the objective and subjective functions are all separable, and the parallel implementation proc...In this paper we discuss the convergence of the directed graph-algorithm for solving a kind of optimization problems where the objective and subjective functions are all separable, and the parallel implementation process for the directed graph -algorithm is introduced.展开更多
文摘基于Petersen图，提出了Binary Tree Petersen的网络结构，并对其特性进行了研究，证明了Binary Tree Petersen网络具有正则性以及良好的可扩展性，同时还具有比RP（k）、2-DToms更短的直径和良好的并行能力．另外，还基于Binary Tree Petersen网络分别给出了其上的单播和广播路由算法，证明了通信效率都为2j＋4．
文摘Most solutions for detecting buffer overflow are based on source code. But the requirement tor source code is not always practical especially for business software. A new approach was presented to detect statically the potential buffer overflow vulnerabilities in the binary code of software. The binary code was translated into assembly code without the lose of the information of string operation functions. The feature code abstract graph was constructed to generate more accurate constraint statements, and analyze the assembly code using the method of integer range constraint. After getting the elementary report on suspicious code where buffer overflows possibly happen, the control flow sensitive analysis using program dependence graph was done to decrease the rate of false positive. A prototype was implemented which demonstrates the feasibility and efficiency of the new approach.
文摘The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decision diagram (ADD) or variants thereof provides canonical forms to represent and manipulate Boolean functions and pseudo-Boolean functions efficiently. ADD and OBDD-based symbolic algorithms give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic ADD formulation and algorithm for maximum weighted matching in bipartite graphs. The symbolic algorithm implements the Hungarian algorithm in the context of ADD and OBDD formulation and manipulations. It begins by setting feasible labelings of nodes and then iterates through a sequence of phases. Each phase is divided into two stages. The first stage is building equality bipartite graphs, and the second one is finding maximum cardinality matching in equality bipartite graph. The second stage iterates through the following steps: greedily searching initial matching, building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. The symbolic algorithm does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments indicate that symbolic algorithm is competitive with traditional algorithms.
文摘Recent years have seen an explosion in graph data from a variety of scientific,social and technological fields.From these fields,emotion recognition is an interesting research area because it finds many applications in real life such as in effective social robotics to increase the interactivity of the robot with human,driver safety during driving,pain monitoring during surgery etc.A novel facial emotion recognition based on graph mining has been proposed in this paper to make a paradigm shift in the way of representing the face region,where the face region is represented as a graph of nodes and edges and the gSpan frequent sub-graphs mining algorithm is used to find the frequent sub-structures in the graph database of each emotion.To reduce the number of generated sub-graphs,overlap ratio metric is utilized for this purpose.After encoding the final selected sub-graphs,binary classification is then applied to classify the emotion of the queried input facial image using six levels of classification.Binary cat swarm intelligence is applied within each level of classification to select proper sub-graphs that give the highest accuracy in that level.Different experiments have been conducted using Surrey Audio-Visual Expressed Emotion(SAVEE)database and the final system accuracy was 90.00%.The results show significant accuracy improvements(about 2%)by the proposed system in comparison to current published works in SAVEE database.
文摘The optimal semi-matching problem is one relaxing form of the maximum cardinality matching problems in bipartite graphs, and finds its applications in load balancing. Ordered binary decision diagram (OBDD) is a canonical form to represent and manipulate Boolean functions efficiently. OBDD-based symbolic algorithms appear to give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic OBDD formulation and algorithm for the optimal semi-matching problem in bipartite graphs. The symbolic algorithm is initialized by heuristic searching initial matching and then iterates through generating residual network, building layered network, backward traversing node-disjoint augmenting paths, and updating semi-matching. It does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Our simulations show that symbolic algorithm has better performance, especially on dense and large graphs.
文摘In this paper, we deduce Wiener number of some connected subgraphs in tilings (4, 4, 4, 4) and (4, 6, 12), which are in Archimedean tilings. And compute their average distance.
文摘In this paper,we consider the NP-hard problem of finding the minimum dominant resolving set of graphs.A vertex set B of a connected graph G resolves G if every vertex of G is uniquely identified by its vector of distances to the vertices in B.A resolving set is dominating if every vertex of G that does not belong to B is a neighbor to some vertices in B.The dominant metric dimension of G is the cardinality number of the minimum dominant resolving set.The dominant metric dimension is computed by a binary version of the Archimedes optimization algorithm(BAOA).The objects of BAOA are binary encoded and used to represent which one of the vertices of the graph belongs to the dominant resolving set.The feasibility is enforced by repairing objects such that an additional vertex generated from vertices of G is added to B and this repairing process is iterated until B becomes the dominant resolving set.This is the first attempt to determine the dominant metric dimension problem heuristically.The proposed BAOA is compared to binary whale optimization(BWOA)and binary particle optimization(BPSO)algorithms.Computational results confirm the superiority of the BAOA for computing the dominant metric dimension.
文摘In this paper we discuss the convergence of the directed graph-algorithm for solving a kind of optimization problems where the objective and subjective functions are all separable, and the parallel implementation process for the directed graph -algorithm is introduced.
