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.展开更多
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.展开更多
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.展开更多
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.展开更多
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.展开更多
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.展开更多
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.展开更多
基金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.
文摘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.
文摘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.
基金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.
文摘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.
文摘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.
文摘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.
