In this paper,the definition of absolutely balanced and uniformly balanced for graphs are introduced,the difference between balance graphs are pointed out.Using（p,p＋1）-graph as an example,we explained the existence...In this paper,the definition of absolutely balanced and uniformly balanced for graphs are introduced,the difference between balance graphs are pointed out.Using（p,p＋1）-graph as an example,we explained the existence of this difference and obtained some new results.展开更多
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.展开更多
Because of cloud computing's high degree of polymerization calculation mode, it can't give full play to the resources of the edge device such as computing, storage, etc. Fog computing can improve the resource ...Because of cloud computing's high degree of polymerization calculation mode, it can't give full play to the resources of the edge device such as computing, storage, etc. Fog computing can improve the resource utilization efficiency of the edge device, and solve the problem about service computing of the delay-sensitive applications. This paper researches on the framework of the fog computing, and adopts Cloud Atomization Technology to turn physical nodes in different levels into virtual machine nodes. On this basis, this paper uses the graph partitioning theory to build the fog computing's load balancing algorithm based on dynamic graph partitioning. The simulation results show that the framework of the fog computing after Cloud Atomization can build the system network flexibly, and dynamic load balancing mechanism can effectively configure system resources as well as reducing the consumption of node migration brought by system changes.展开更多
We prove that a random labeled (unlabeled) tree is balanced. We also prove that random labeled and unlabeled trees are strongly k-balanced for any k ≥ 3. Definition: Color the vertices ...We prove that a random labeled (unlabeled) tree is balanced. We also prove that random labeled and unlabeled trees are strongly k-balanced for any k ≥ 3. Definition: Color the vertices of graph G with two colors. Color an edge with the color of its endpoints if they are colored with the same color. Edges with different colored endpoints are left uncolored. G is said to be balanced if neither the number of vertices nor and the number of edges of the two different colors differs by more than one.展开更多
目的研究视觉对人体姿势控制影响及其脑功能网络连接机制。方法以15名健康青年为研究对象,要求受试者分别进行30 s睁眼、闭眼的双腿站立平衡,采集平衡过程中身体压力中心(center of pressure,COP)和脑电。对COP进行样本熵(SampleEn)计算...目的研究视觉对人体姿势控制影响及其脑功能网络连接机制。方法以15名健康青年为研究对象,要求受试者分别进行30 s睁眼、闭眼的双腿站立平衡,采集平衡过程中身体压力中心(center of pressure,COP)和脑电。对COP进行样本熵(SampleEn)计算;对脑电θ、α和β频段,计算相位滞后指数(phase lag index,PLI)构建大脑功能网络,并基于图论计算集聚系数(C)、特征路径长度(L)及小世界网络属性(σ)。结果人体在双腿站立平衡过程中,闭眼COPY样本熵显著高于睁眼(P<0.05)。闭眼α频段PLI平均值显著高于睁眼(P<0.05);闭眼α频段C、σ显著高于睁眼,L显著低于睁眼(P<0.05)。闭眼时α频段额区-中央区-顶区之间的网络连接以及中央区和顶区内连接强度显著高于睁眼(P<0.05)。闭眼时α频段PLI平均值以及C值与COPY样本熵中度呈中度负相关(P<0.05)。睁眼时左前额区、左顶区、左枕区α频段PLI平均值与COPY样本熵呈中度负相关;闭眼时左中央区、右枕区α频段PLI平均值则与COPY样本熵呈中度负相关。结论人体在站立平衡时,当没有视觉信息输入时,身体平衡稳定性下降,同时伴随着脑电α频段的脑网络连接增强以及大脑处理信息的效率需提升。人体在不同的视觉条件下进行姿势控制时,大脑会采用不同的神经策略。展开更多
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.展开更多
作为诸多移动机器人应用的基础,完全覆盖旨在为机器人规划出一条访问目标区域所有点且耗时最短的无碰撞路径。此类覆盖应用中,利用多台机器人协同覆盖可以有效缩短覆盖时间并提升系统的鲁棒性,同时也增加了算法设计复杂度和机器人协同...作为诸多移动机器人应用的基础,完全覆盖旨在为机器人规划出一条访问目标区域所有点且耗时最短的无碰撞路径。此类覆盖应用中,利用多台机器人协同覆盖可以有效缩短覆盖时间并提升系统的鲁棒性,同时也增加了算法设计复杂度和机器人协同管理难度。因此,文中研究了已知环境下的多机器人覆盖问题,该问题已被证明是一个NP难题。文中提出了一种启发式的基于多层次图划分的多机器人任务分配方法(Multi-robot Task Assignment Based on Multi-level Graph Partitioning,TAMP),该方法包含一种粗化任务分配算法和一种精细任务分配算法。粗化任务分配算法采用分层粗化的方法,通过图的极大匹配实现了节点融合以降低图的规模,并基于均匀种子的图增长方式获取了一个接近均衡的初始任务分配结果,提高算法效率;精细任务分配算法在粗化任务分配算法的基础上,提出了一种基于边界节点交换的Lazy&Lock策略,用于实现任务细分,提高求解精度。文中在不同规模的随机图和真实世界的治安巡逻场景下进行了仿真验证。仿真结果表明,相比经典的任务分配方法,TAMP方法将可求解的最大计算规模从千级扩大到百万级,小规模图(3000以内)的计算速度加快了20倍,距离最优解偏差均优于经典方法;能够在60 s内解决大规模图(3000~1000000)的任务分配问题,同时将距离最优解偏差控制在0.3%以内。展开更多
基金Supported by the Natural Science Foundation of Shanxi Province（2008011010） Supported by the Scientific Research and Key Subject Foundation of University of Science and Technology of Suzhou
文摘In this paper,the definition of absolutely balanced and uniformly balanced for graphs are introduced,the difference between balance graphs are pointed out.Using（p,p＋1）-graph as an example,we explained the existence of this difference and obtained some new results.
文摘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.
基金supported in part by the National Science and technology support program of P.R.China(No.2014BAH29F05)
文摘Because of cloud computing's high degree of polymerization calculation mode, it can't give full play to the resources of the edge device such as computing, storage, etc. Fog computing can improve the resource utilization efficiency of the edge device, and solve the problem about service computing of the delay-sensitive applications. This paper researches on the framework of the fog computing, and adopts Cloud Atomization Technology to turn physical nodes in different levels into virtual machine nodes. On this basis, this paper uses the graph partitioning theory to build the fog computing's load balancing algorithm based on dynamic graph partitioning. The simulation results show that the framework of the fog computing after Cloud Atomization can build the system network flexibly, and dynamic load balancing mechanism can effectively configure system resources as well as reducing the consumption of node migration brought by system changes.
文摘We prove that a random labeled (unlabeled) tree is balanced. We also prove that random labeled and unlabeled trees are strongly k-balanced for any k ≥ 3. Definition: Color the vertices of graph G with two colors. Color an edge with the color of its endpoints if they are colored with the same color. Edges with different colored endpoints are left uncolored. G is said to be balanced if neither the number of vertices nor and the number of edges of the two different colors differs by more than one.
文摘目的研究视觉对人体姿势控制影响及其脑功能网络连接机制。方法以15名健康青年为研究对象,要求受试者分别进行30 s睁眼、闭眼的双腿站立平衡,采集平衡过程中身体压力中心(center of pressure,COP)和脑电。对COP进行样本熵(SampleEn)计算;对脑电θ、α和β频段,计算相位滞后指数(phase lag index,PLI)构建大脑功能网络,并基于图论计算集聚系数(C)、特征路径长度(L)及小世界网络属性(σ)。结果人体在双腿站立平衡过程中,闭眼COPY样本熵显著高于睁眼(P<0.05)。闭眼α频段PLI平均值显著高于睁眼(P<0.05);闭眼α频段C、σ显著高于睁眼,L显著低于睁眼(P<0.05)。闭眼时α频段额区-中央区-顶区之间的网络连接以及中央区和顶区内连接强度显著高于睁眼(P<0.05)。闭眼时α频段PLI平均值以及C值与COPY样本熵中度呈中度负相关(P<0.05)。睁眼时左前额区、左顶区、左枕区α频段PLI平均值与COPY样本熵呈中度负相关;闭眼时左中央区、右枕区α频段PLI平均值则与COPY样本熵呈中度负相关。结论人体在站立平衡时,当没有视觉信息输入时,身体平衡稳定性下降,同时伴随着脑电α频段的脑网络连接增强以及大脑处理信息的效率需提升。人体在不同的视觉条件下进行姿势控制时,大脑会采用不同的神经策略。
文摘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.
文摘作为诸多移动机器人应用的基础,完全覆盖旨在为机器人规划出一条访问目标区域所有点且耗时最短的无碰撞路径。此类覆盖应用中,利用多台机器人协同覆盖可以有效缩短覆盖时间并提升系统的鲁棒性,同时也增加了算法设计复杂度和机器人协同管理难度。因此,文中研究了已知环境下的多机器人覆盖问题,该问题已被证明是一个NP难题。文中提出了一种启发式的基于多层次图划分的多机器人任务分配方法(Multi-robot Task Assignment Based on Multi-level Graph Partitioning,TAMP),该方法包含一种粗化任务分配算法和一种精细任务分配算法。粗化任务分配算法采用分层粗化的方法,通过图的极大匹配实现了节点融合以降低图的规模,并基于均匀种子的图增长方式获取了一个接近均衡的初始任务分配结果,提高算法效率;精细任务分配算法在粗化任务分配算法的基础上,提出了一种基于边界节点交换的Lazy&Lock策略,用于实现任务细分,提高求解精度。文中在不同规模的随机图和真实世界的治安巡逻场景下进行了仿真验证。仿真结果表明,相比经典的任务分配方法,TAMP方法将可求解的最大计算规模从千级扩大到百万级,小规模图(3000以内)的计算速度加快了20倍,距离最优解偏差均优于经典方法;能够在60 s内解决大规模图(3000~1000000)的任务分配问题,同时将距离最优解偏差控制在0.3%以内。
