This paper proposes a new method for dynamic airspace configuration based on a weighted graph model. The method begins with the construction of an undirected graph for the given airspace, where the vertices represent ...This paper proposes a new method for dynamic airspace configuration based on a weighted graph model. The method begins with the construction of an undirected graph for the given airspace, where the vertices represent those key points such as airports, waypoints, and the edges represent those air routes. Those vertices are used as the sites of Voronoi diagram, which divides the airspace into units called as cells. Then, aircraft counts of both each cell and of each air-route are computed. Thus, by assigning both the vertices and the edges with those aircraft counts, a weighted graph model comes into being. Accordingly the airspace configuration problem is described as a weighted graph partitioning problem. Then, the problem is solved by a graph partitioning algorithm, which is a mixture of general weighted graph cuts algorithm, an optimal dynamic load balancing algorithm and a heuristic algorithm. After the cuts algorithm partitions the model into sub-graphs, the load balancing algorithm together with the heuristic algorithm transfers aircraft counts to balance workload among sub-graphs. Lastly, airspace configuration is completed by determining the sector boundaries. The simulation result shows that the designed sectors satisfy not only workload balancing condition, but also the constraints such as convexity, connectivity, as well as minimum distance constraint.展开更多
This paper proposes an algorithm for building weighted directed graph, defmes the weighted directed relationship matrix of the graph, and describes algorithm implementation using this matrix. Based on this algorithm, ...This paper proposes an algorithm for building weighted directed graph, defmes the weighted directed relationship matrix of the graph, and describes algorithm implementation using this matrix. Based on this algorithm, an effective way for building and drawing weighted directed graphs is presented, forming a foundation for visual implementation of the algorithm in the graph theory.展开更多
Timed weighted marked graphs are a subclass of timed Petri nets that have wide applications in the control and performance analysis of flexible manufacturing systems.Due to the existence of multiplicities(i.e.,weights...Timed weighted marked graphs are a subclass of timed Petri nets that have wide applications in the control and performance analysis of flexible manufacturing systems.Due to the existence of multiplicities(i.e.,weights)on edges,the performance analysis and resource optimization of such graphs represent a challenging problem.In this paper,we develop an approach to transform a timed weighted marked graph whose initial marking is not given,into an equivalent parametric timed marked graph where the edges have unitary weights.In order to explore an optimal resource allocation policy for a system,an analytical method is developed for the resource optimization of timed weighted marked graphs by studying an equivalent net.Finally,we apply the proposed method to a flexible manufacturing system and compare the results with a previous heuristic approach.Simulation analysis shows that the developed approach is superior to the heuristic approach.展开更多
Structural robustness is the concept to evaluate whether local damages to the structure will cause disproportional consequences. It is one of the most important indexes to keep the structural safety, especially to con...Structural robustness is the concept to evaluate whether local damages to the structure will cause disproportional consequences. It is one of the most important indexes to keep the structural safety, especially to consider a special loading named as "human active damage". In the present paper, the loaded structure is analyzed by a weighted graph. The joints and members of the structure correspond to the vertexes and edges of the graph, and the ratio of the most dangerous stress state to the material strength of each member is treated as the weight of each edge. Based on the quantitative description of the structural topology, the structure graph is expressed as a hierarchical model which is built by a set of vertex-connected units. The local damage can be expressed as the deterioration of the unit(s), while the final possible failure mode of the structure can be obtained by a specific assignment of its weighted graph. In this way, the relationship between the structural behavior and the combined damages of the subordinate units in each hierarchy can be formed as an envelope diagram. This diagram exactly shows the contribution of each subordinate unit to the robustness of the whole structure. Furthermore, the most vulnerable part, as well as the topologic difference between the subordinates, can be found visually.展开更多
We study the spin squeezing property of weighted graph states,which can be used to improve sensitivity in interferometry.We study the time evolution of spin squeezing under local decoherence acting independently on ea...We study the spin squeezing property of weighted graph states,which can be used to improve sensitivity in interferometry.We study the time evolution of spin squeezing under local decoherence acting independently on each qubit.Based on the analysis,the spin squeezing of the weighted graph states is somehow robust in the presence of decoherence and the decoherence limit in the improvement of the interferometric sensitivity is still achievable.Furthermore,one can obtain the optimal improvement of sensitivity by tuning the weighted of each edges of the weighted graph state.展开更多
The notion of w-density for the graphs with positive weights on vertices and nonnegative weights on edges is introduced.A weighted graph is called w-balanced if its w-density is no less than the w-density of any subgr...The notion of w-density for the graphs with positive weights on vertices and nonnegative weights on edges is introduced.A weighted graph is called w-balanced if its w-density is no less than the w-density of any subgraph of it.In this paper,a good characterization of w-balanced weighted graphs is given.Applying this characterization,many large w-balanced weighted graphs are formed by combining smaller ones.In the case where a graph is not w-balanced,a polynomial-time algorithm to find a subgraph of maximum w-density is proposed.It is shown that the w-density theory is closely related to the study of SEW(G,w) games.展开更多
In this paper we give a Dirac type condition for heavy cycles in a 3-connected weighted graph, reading that if d^w（v）≥ d for all v ∈ V（G）／{x} and w（uz） = w（vz）, when uz, vz ∈ E（G） and uv ∈/ E（G）. Then...In this paper we give a Dirac type condition for heavy cycles in a 3-connected weighted graph, reading that if d^w（v）≥ d for all v ∈ V（G）／{x} and w（uz） = w（vz）, when uz, vz ∈ E（G） and uv ∈/ E（G）. Then G contains either an （x, y）-cycle of weight at least 2d or a Hamilton cycle.展开更多
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.展开更多
In this study, the SK, SK<sub>1</sub> and SK<sub>2</sub> indices are defined on weighted graphs. Then, the SK, SK<sub>1</sub> and SK<sub>2</sub> indices are defined on i...In this study, the SK, SK<sub>1</sub> and SK<sub>2</sub> indices are defined on weighted graphs. Then, the SK, SK<sub>1</sub> and SK<sub>2</sub> indices are defined on interval weighted graphs. Their behaviors are investigated under some graph operations by using these definitions.展开更多
The virial expansion, in statistical mechanics, makes use of the sums of the Mayer weight of all 2-connected graphs on n vertices. We study the Second Mayer weight ωM(c) and the Ree-Hoover weight ωRH(c) of a 2-conne...The virial expansion, in statistical mechanics, makes use of the sums of the Mayer weight of all 2-connected graphs on n vertices. We study the Second Mayer weight ωM(c) and the Ree-Hoover weight ωRH(c) of a 2-connected graph c which arise from the hard-core continuum gas in one dimension. These weights are computed using signed volumes of convex polytopes naturally associated with the graph c. In the present work, we use the method of graph homomorphisms, to give new formulas of Mayer and Ree-Hoover weights for special infinite families of 2-connected graphs.展开更多
We study graph weights which naturally occur in Mayer’s theory and Ree-Hoover’s theory for the virial expansion in the context of an imperfect gas. We pay particular attention to the Mayer weight and Ree-Hoover weig...We study graph weights which naturally occur in Mayer’s theory and Ree-Hoover’s theory for the virial expansion in the context of an imperfect gas. We pay particular attention to the Mayer weight and Ree-Hoover weight of a 2-connected graph in the case of the hard-core continuum gas in one dimension. These weights are calculated from signed volumes of convex polytopes associated with the graph. In the present paper, we use the method of graph homomorphisms, to develop other explicit formulas of Mayer weights and Ree-Hoover weights for infinite families of 2-connected graphs.展开更多
Based on the definition of class shortest path in weighted rough graph, class shortest path algorithm in weighted rough graph is presented, which extends classical shortest path algorithm. The application in relations...Based on the definition of class shortest path in weighted rough graph, class shortest path algorithm in weighted rough graph is presented, which extends classical shortest path algorithm. The application in relationship mining shows effectiveness of it.展开更多
This paper researched into some methods for generating min-weighted rigid graphs and min-weighted persistent graphs. Rigidity and persistence are currently used in various studies on coordination and control of autono...This paper researched into some methods for generating min-weighted rigid graphs and min-weighted persistent graphs. Rigidity and persistence are currently used in various studies on coordination and control of autonomous multi-agent formations. To minimize the communication complexity of formations and reduce energy consumption, this paper introduces the rigidity matrix and presents three algorithms for generating rain-weighted rigid and min- weighted persistent graphs. First, the existence of a min-weighted rigid graph is proved by using the rigidity matrix, and algorithm 1 is presented to generate the min-weighted rigid graphs. Second, the algorithm 2 based on the rigidity matrix is presented to direct the edges of min-weighted rigid graphs to generate min-weighted persistent graphs. Third, the formations with range constraints are considered, and algorithm 3 is presented to find whether a framework can form a min-weighted persistent formation. Finally, some simulations are given to show the efficiency of our research.展开更多
The design synthesis is the key issue in the mechanical conceptual design to generate the design candidates that meet the design requirements.This paper devotes to propose a novel and computable synthesis approach of ...The design synthesis is the key issue in the mechanical conceptual design to generate the design candidates that meet the design requirements.This paper devotes to propose a novel and computable synthesis approach of mechanisms based on graph theory and polynomial operation.The graph framework of the synthesis approach is built firstly,and it involves:(1)the kinematic function units extracted from mechanisms;(2)the kinematic link graph that transforms the synthesis problem from mechanical domain into graph domain;(3)two graph representations,i.e.,walk representation and path representation,of design candidates;(4)a weighted matrix theorem that transforms the synthesis process into polynomial operation.Then,the formulas and algorithm to the polynomial operation are presented.Based on them,the computational flowchart to the synthesis approach is summarized.A design example is used to validate and illustrate the synthesis approach in detail.The proposed synthesis approach is not only supportive to enumerate the design candidates to the conceptual design of a mechanical system exhaustively and automatically,but also helpful to make that enumeration process computable.展开更多
Traveltime tomography is a technique to reconstruct acoustic, seismic, or electromagnetic wave-speed distributions from first arrival traveltime data. The ray paths that should be used for tomographic techniques stro...Traveltime tomography is a technique to reconstruct acoustic, seismic, or electromagnetic wave-speed distributions from first arrival traveltime data. The ray paths that should be used for tomographic techniques strongly depend on the wave-speed distribution. In this paper, a new method is proposed for finding out the ray paths from Fermat's principle, that means the traveltime of the ray path should be a minimum value. The problem of finding out the ray path is actually an optimum problem. Our new method uses the idea to find out the shortest path in a weighted directed graph to solve the problem. The ray paths found out by this method are used in the iterative reconstruction algorithm. Computer simulation result produced by this reconstruction algorithm is better than that by the conventional ones. It also shows that the new algorithm is effective with good convergency and stability.展开更多
基金supported by the National Natural Science Foundationof China(No.61079001)
文摘This paper proposes a new method for dynamic airspace configuration based on a weighted graph model. The method begins with the construction of an undirected graph for the given airspace, where the vertices represent those key points such as airports, waypoints, and the edges represent those air routes. Those vertices are used as the sites of Voronoi diagram, which divides the airspace into units called as cells. Then, aircraft counts of both each cell and of each air-route are computed. Thus, by assigning both the vertices and the edges with those aircraft counts, a weighted graph model comes into being. Accordingly the airspace configuration problem is described as a weighted graph partitioning problem. Then, the problem is solved by a graph partitioning algorithm, which is a mixture of general weighted graph cuts algorithm, an optimal dynamic load balancing algorithm and a heuristic algorithm. After the cuts algorithm partitions the model into sub-graphs, the load balancing algorithm together with the heuristic algorithm transfers aircraft counts to balance workload among sub-graphs. Lastly, airspace configuration is completed by determining the sector boundaries. The simulation result shows that the designed sectors satisfy not only workload balancing condition, but also the constraints such as convexity, connectivity, as well as minimum distance constraint.
基金Project supported by Science Foundation of Shanghai MunicipalConmission of Education (Grant No .03A203)
文摘This paper proposes an algorithm for building weighted directed graph, defmes the weighted directed relationship matrix of the graph, and describes algorithm implementation using this matrix. Based on this algorithm, an effective way for building and drawing weighted directed graphs is presented, forming a foundation for visual implementation of the algorithm in the graph theory.
基金supported by the National Natural Science Foundation of China(61803246,61703321)the China Postdoctoral Science Foundation(2019M663608)+2 种基金Shaanxi Provincial Natural Science Foundation(2019JQ-022,2020JQ-733)the Fundamental Research Funds for the Central Universities(JB190407)the Shaanxi Key Laboratory of Complex System Control and Intelligent Information Processing,Xi’an University of Technology(SKL2020CP03)。
文摘Timed weighted marked graphs are a subclass of timed Petri nets that have wide applications in the control and performance analysis of flexible manufacturing systems.Due to the existence of multiplicities(i.e.,weights)on edges,the performance analysis and resource optimization of such graphs represent a challenging problem.In this paper,we develop an approach to transform a timed weighted marked graph whose initial marking is not given,into an equivalent parametric timed marked graph where the edges have unitary weights.In order to explore an optimal resource allocation policy for a system,an analytical method is developed for the resource optimization of timed weighted marked graphs by studying an equivalent net.Finally,we apply the proposed method to a flexible manufacturing system and compare the results with a previous heuristic approach.Simulation analysis shows that the developed approach is superior to the heuristic approach.
文摘Structural robustness is the concept to evaluate whether local damages to the structure will cause disproportional consequences. It is one of the most important indexes to keep the structural safety, especially to consider a special loading named as "human active damage". In the present paper, the loaded structure is analyzed by a weighted graph. The joints and members of the structure correspond to the vertexes and edges of the graph, and the ratio of the most dangerous stress state to the material strength of each member is treated as the weight of each edge. Based on the quantitative description of the structural topology, the structure graph is expressed as a hierarchical model which is built by a set of vertex-connected units. The local damage can be expressed as the deterioration of the unit(s), while the final possible failure mode of the structure can be obtained by a specific assignment of its weighted graph. In this way, the relationship between the structural behavior and the combined damages of the subordinate units in each hierarchy can be formed as an envelope diagram. This diagram exactly shows the contribution of each subordinate unit to the robustness of the whole structure. Furthermore, the most vulnerable part, as well as the topologic difference between the subordinates, can be found visually.
基金Project supported by the National Natural Science Foundation of China (Grant Nos. 11004029 and 11174052)the Natural Science Foundation of Jiangsu Province of China (Grant No. BK2010422)+2 种基金the Ph. D. Program of the Ministry of Education of Chinathe Excellent Young Teachers Program of Southeast Universitythe National Basic Research Development Program of China(Grant No. 2011CB921203)
文摘We study the spin squeezing property of weighted graph states,which can be used to improve sensitivity in interferometry.We study the time evolution of spin squeezing under local decoherence acting independently on each qubit.Based on the analysis,the spin squeezing of the weighted graph states is somehow robust in the presence of decoherence and the decoherence limit in the improvement of the interferometric sensitivity is still achievable.Furthermore,one can obtain the optimal improvement of sensitivity by tuning the weighted of each edges of the weighted graph state.
文摘The notion of w-density for the graphs with positive weights on vertices and nonnegative weights on edges is introduced.A weighted graph is called w-balanced if its w-density is no less than the w-density of any subgraph of it.In this paper,a good characterization of w-balanced weighted graphs is given.Applying this characterization,many large w-balanced weighted graphs are formed by combining smaller ones.In the case where a graph is not w-balanced,a polynomial-time algorithm to find a subgraph of maximum w-density is proposed.It is shown that the w-density theory is closely related to the study of SEW(G,w) games.
文摘In this paper we give a Dirac type condition for heavy cycles in a 3-connected weighted graph, reading that if d^w（v）≥ d for all v ∈ V（G）／{x} and w（uz） = w（vz）, when uz, vz ∈ E（G） and uv ∈/ E（G）. Then G contains either an （x, y）-cycle of weight at least 2d or a Hamilton cycle.
文摘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.
文摘In this study, the SK, SK<sub>1</sub> and SK<sub>2</sub> indices are defined on weighted graphs. Then, the SK, SK<sub>1</sub> and SK<sub>2</sub> indices are defined on interval weighted graphs. Their behaviors are investigated under some graph operations by using these definitions.
文摘The virial expansion, in statistical mechanics, makes use of the sums of the Mayer weight of all 2-connected graphs on n vertices. We study the Second Mayer weight ωM(c) and the Ree-Hoover weight ωRH(c) of a 2-connected graph c which arise from the hard-core continuum gas in one dimension. These weights are computed using signed volumes of convex polytopes naturally associated with the graph c. In the present work, we use the method of graph homomorphisms, to give new formulas of Mayer and Ree-Hoover weights for special infinite families of 2-connected graphs.
文摘We study graph weights which naturally occur in Mayer’s theory and Ree-Hoover’s theory for the virial expansion in the context of an imperfect gas. We pay particular attention to the Mayer weight and Ree-Hoover weight of a 2-connected graph in the case of the hard-core continuum gas in one dimension. These weights are calculated from signed volumes of convex polytopes associated with the graph. In the present paper, we use the method of graph homomorphisms, to develop other explicit formulas of Mayer weights and Ree-Hoover weights for infinite families of 2-connected graphs.
基金Natural Science Foundation of Shandong Province of China (Y2004A04)Natural Science Foundation of Shandong Province of China (Y2006A12)Foundation of Ministry of Fujian Province Education of China (JA04268).
文摘Based on the definition of class shortest path in weighted rough graph, class shortest path algorithm in weighted rough graph is presented, which extends classical shortest path algorithm. The application in relationship mining shows effectiveness of it.
基金supported by the National Natural Science Foundation for Distinguished Young Scholars of China (Grant No 60525303)the National Natural Science Foundation of China (Grant No 60704009)Doctor Fund of Yanshan University (Grant NoB203)
文摘This paper researched into some methods for generating min-weighted rigid graphs and min-weighted persistent graphs. Rigidity and persistence are currently used in various studies on coordination and control of autonomous multi-agent formations. To minimize the communication complexity of formations and reduce energy consumption, this paper introduces the rigidity matrix and presents three algorithms for generating rain-weighted rigid and min- weighted persistent graphs. First, the existence of a min-weighted rigid graph is proved by using the rigidity matrix, and algorithm 1 is presented to generate the min-weighted rigid graphs. Second, the algorithm 2 based on the rigidity matrix is presented to direct the edges of min-weighted rigid graphs to generate min-weighted persistent graphs. Third, the formations with range constraints are considered, and algorithm 3 is presented to find whether a framework can form a min-weighted persistent formation. Finally, some simulations are given to show the efficiency of our research.
基金Supported by State Key Program of National Natural Science Foundation of China(Grant No.51535009)111 Project of China(Grant No.B13044).
文摘The design synthesis is the key issue in the mechanical conceptual design to generate the design candidates that meet the design requirements.This paper devotes to propose a novel and computable synthesis approach of mechanisms based on graph theory and polynomial operation.The graph framework of the synthesis approach is built firstly,and it involves:(1)the kinematic function units extracted from mechanisms;(2)the kinematic link graph that transforms the synthesis problem from mechanical domain into graph domain;(3)two graph representations,i.e.,walk representation and path representation,of design candidates;(4)a weighted matrix theorem that transforms the synthesis process into polynomial operation.Then,the formulas and algorithm to the polynomial operation are presented.Based on them,the computational flowchart to the synthesis approach is summarized.A design example is used to validate and illustrate the synthesis approach in detail.The proposed synthesis approach is not only supportive to enumerate the design candidates to the conceptual design of a mechanical system exhaustively and automatically,but also helpful to make that enumeration process computable.
文摘Traveltime tomography is a technique to reconstruct acoustic, seismic, or electromagnetic wave-speed distributions from first arrival traveltime data. The ray paths that should be used for tomographic techniques strongly depend on the wave-speed distribution. In this paper, a new method is proposed for finding out the ray paths from Fermat's principle, that means the traveltime of the ray path should be a minimum value. The problem of finding out the ray path is actually an optimum problem. Our new method uses the idea to find out the shortest path in a weighted directed graph to solve the problem. The ray paths found out by this method are used in the iterative reconstruction algorithm. Computer simulation result produced by this reconstruction algorithm is better than that by the conventional ones. It also shows that the new algorithm is effective with good convergency and stability.
