Wireless sensor networks are suffering from serious frequency interference.In this paper,we propose a channel assignment algorithm based on graph theory in wireless sensor networks.We first model the conflict infectio...Wireless sensor networks are suffering from serious frequency interference.In this paper,we propose a channel assignment algorithm based on graph theory in wireless sensor networks.We first model the conflict infection graph for channel assignment with the goal of global optimization minimizing the total interferences in wireless sensor networks.The channel assignment problem is equivalent to the generalized graph-coloring problem which is a NP-complete problem.We further present a meta-heuristic Wireless Sensor Network Parallel Tabu Search(WSN-PTS) algorithm,which can optimize global networks with small numbers of iterations.The results from a simulation experiment reveal that the novel algorithm can effectively solve the channel assignment problem.展开更多
To solve the deadlock problem of tasks that the interdependence between tasks fails to consider during the course of resource assignment and task scheduling based on the heuristics algorithm, an improved ant colony sy...To solve the deadlock problem of tasks that the interdependence between tasks fails to consider during the course of resource assignment and task scheduling based on the heuristics algorithm, an improved ant colony system （ACS） based algorithm is proposed. First, how to map the resource assignment and task scheduling （RATS） problem into the optimization selection problem of task resource assignment graph （TRAG） and to add the semaphore mechanism in the optimal TRAG to solve deadlocks are explained. Secondly, how to utilize the grid pheromone system model to realize the algorithm based on ACS is explicated. This refers to the construction of TRAG by the random selection of appropriate resources for each task by the user agent and the optimization of TRAG through the positive feedback and distributed parallel computing mechanism of the ACS. Simulation results show that the proposed algorithm is effective and efficient in solving the deadlock problem.展开更多
In order to solve the problem of efficiently assigning tasks in an ad-hoc mobile cloud( AMC),a task assignment algorithm based on the heuristic algorithm is proposed. The proposed task assignment algorithm based on pa...In order to solve the problem of efficiently assigning tasks in an ad-hoc mobile cloud( AMC),a task assignment algorithm based on the heuristic algorithm is proposed. The proposed task assignment algorithm based on particle swarm optimization and simulated annealing( PSO-SA) transforms the dependencies between tasks into a directed acyclic graph( DAG) model. The number in each node represents the computation workload of each task and the number on each edge represents the workload produced by the transmission. In order to simulate the environment of task assignment in AMC,mathematical models are developed to describe the dependencies between tasks and the costs of each task are defined. PSO-SA is used to make the decision for task assignment and for minimizing the cost of all devices,which includes the energy consumption and time delay of all devices.PSO-SA also takes the advantage of both particle swarm optimization and simulated annealing by selecting an optimal solution with a certain probability to avoid falling into local optimal solution and to guarantee the convergence speed. The simulation results show that compared with other existing algorithms,the PSO-SA has a smaller cost and the result of PSO-SA can be very close to the optimal solution.展开更多
An L（2, 1）-labeling of a graph G is a function f from the vertex set V（G） to the set of all nonnegative integers such that ｜f（x） - f（y）｜ 〉 2 if d（x, y） = 1 and ｜f（x）-f（y）｜ ≥ 1 ifd（x, y） = 2. The ...An L（2, 1）-labeling of a graph G is a function f from the vertex set V（G） to the set of all nonnegative integers such that ｜f（x） - f（y）｜ 〉 2 if d（x, y） = 1 and ｜f（x）-f（y）｜ ≥ 1 ifd（x, y） = 2. The L（2, 1）-labeling number λ（G） of G is the smallest number k such that G has an L（2, 1）-labeling with max{f（v） ： v ∈ V（G）} = k. We study the L（3, 2, 1）-labeling which is a generalization of the L（2, 1）-labeling on the graph formed by the （Cartesian） product and composition of 3 graphs and derive the upper bounds of λ3（G） of the graph.展开更多
Discusses how to assign a set of noninterference radio channels to a symmetric network of transmitter location over a large planar area, the minimum of the span and the assignment of the channels with the changing of ...Discusses how to assign a set of noninterference radio channels to a symmetric network of transmitter location over a large planar area, the minimum of the span and the assignment of the channels with the changing of minimum distance among the same channels and the changing of the minimum difference among the adjacent channels. The minimum interval in the frequency spectrum of 9 interger channels is proved and obtained by using the graphic theory and the reduction to absurdity on condition that interference from nearby transmitters is avoided in the whole given grid and the grid spreading arbitrarily far in all directions.展开更多
Solving the absent assignment problem of the shortest time limit in a weighted bipartite graph with the minimal weighted k-matching algorithm is unsuitable for situations in which large numbers of problems need to be ...Solving the absent assignment problem of the shortest time limit in a weighted bipartite graph with the minimal weighted k-matching algorithm is unsuitable for situations in which large numbers of problems need to be addressed by large numbers of parties. This paper simplifies the algorithm of searching for the even alternating path that contains a maximal element using the minimal weighted k-matching theorem and intercept graph. A program for solving the maximal efficiency assignment problem was compiled. As a case study, the program was used to solve the assignment problem of water piping repair in the case of a large number of companies and broken pipes, and the validity of the program was verified.展开更多
A variety of problems in digital circuits, computer networks, automated manufacturing plants, etc., can be modeled as min-max systems. The cycle time is an important performance metric of such systems. In this paper, ...A variety of problems in digital circuits, computer networks, automated manufacturing plants, etc., can be modeled as min-max systems. The cycle time is an important performance metric of such systems. In this paper, we focus on the cycle time assignment of minimax systems which corresponds to the pole assignment problem in traditional linear control systems. For the min- max system with max-plus inputs and outputs, we show that the cycle time can be assigned disjointedly by a state feedback, if and only if the system is reachable. Furthermore, a necessary and sufficient condition for the cycle time to be assigned independently by a state feedback is given. The methods are constructive, and some numerical examples are given to illustrate how the methods work in practice.展开更多
L (2, 1)-labeling number, λ(G( Z , D)) , of distance graph G( Z , D) is studied. For general finite distance set D , it is shown that 2D+2≤λ(G( Z , D))≤D 2+3D. Furthermore, λ(G( Z , D)) ≤8 when...L (2, 1)-labeling number, λ(G( Z , D)) , of distance graph G( Z , D) is studied. For general finite distance set D , it is shown that 2D+2≤λ(G( Z , D))≤D 2+3D. Furthermore, λ(G( Z , D)) ≤8 when D consists of two prime positive odd integers is proved. Finally, a new concept to study the upper bounds of λ(G) for some special D is introduced. For these sets, the upper bound is improved to 7.展开更多
The L(2,1)-labelling number of distance graphs G(D), denoted by λ(D), isstudied. It is shown that distance graphs satisfy λ(G) ≤Δ~2. Moreover, we prove λ({1,2, ..., k})=2k +2 and λ({1,3,..., 2k -1}) =2k + 2 for ...The L(2,1)-labelling number of distance graphs G(D), denoted by λ(D), isstudied. It is shown that distance graphs satisfy λ(G) ≤Δ~2. Moreover, we prove λ({1,2, ..., k})=2k +2 and λ({1,3,..., 2k -1}) =2k + 2 for any fixed positive integer k. Suppose k, a ∈ N and k,a≥2. If k≥a, then λ({a, a + 1,..., a + k - 1}) = 2(a + k-1). Otherwise, λ({a, a + 1, ..., a + k- 1}) ≤min{2(a + k-1), 6k -2}. When D consists of two positive integers,6≤λ(D)≤8. For thespecial distance sets D = {k, k + 1}(any k ∈N), the upper bound of λ(D) is improved to 7.展开更多
An L(0,1)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between the labels assigned to any two adjacent vertices is at least zero and the difference betw...An L(0,1)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between the labels assigned to any two adjacent vertices is at least zero and the difference between the labels assigned to any two vertices which are at distance two is at least one. The span of an L(0,1)-labelling is the maximum label number assigned to any vertex of G. The L(0,1)-labelling number of a graph G, denoted by λ0.1(G) is the least integer k such that G has an L(0,1)-labelling of span k. This labelling has an application to a computer code assignment problem. The task is to assign integer control codes to a network of computer stations with distance restrictions. A cactus graph is a connected graph in which every block is either an edge or a cycle. In this paper, we label the vertices of a cactus graph by L(0,1)-labelling and have shown that, △-1≤λ0.1(G)≤△ for a cactus graph, where △ is the degree of the graph G.展开更多
An L（3, 2, 1）-labeling of a graph G is a function from the vertex set V（G） to the set of all nonnegative integers such that ｜f（u）-f（v）｜≥3 if dG（u,v） = 1, ｜f（u）-f（v）｜≥2 if dG（u,v） = 2, and ｜f（u...An L（3, 2, 1）-labeling of a graph G is a function from the vertex set V（G） to the set of all nonnegative integers such that ｜f（u）-f（v）｜≥3 if dG（u,v） = 1, ｜f（u）-f（v）｜≥2 if dG（u,v） = 2, and ｜f（u）-f（v）｜≥1 if dG（u,v） = 3. The L（3, 2,1）-labeling problem is to find the smallest number λ3（G） such that there exists an L（3, 2,1）-labeling function with no label greater than it. This paper studies the problem for bipartite graphs. We obtain some bounds of λ3 for bipartite graphs and its subclasses. Moreover, we provide a best possible condition for a tree T such that λ3（T） attains the minimum value.展开更多
A k-L(2,1)-labeling for a graph G is a function such that whenever and whenever u and v are at distance two apart. The λ-number for G, denoted by λ(G), is the minimum k over all k-L(2,1)-labelings of G. In this pape...A k-L(2,1)-labeling for a graph G is a function such that whenever and whenever u and v are at distance two apart. The λ-number for G, denoted by λ(G), is the minimum k over all k-L(2,1)-labelings of G. In this paper, we show that for or 11, which confirms Conjecture 6.1 stated in [X. Li, V. Mak-Hau, S. Zhou, The L(2,1)-labelling problem for cubic Cayley graphs on dihedral groups, J. Comb. Optim. (2013) 25: 716-736] in the case when or 11. Moreover, we show that? if 1) either (mod 6), m is odd, r = 3, or 2) (mod 3), m is even (mod 2), r = 0.展开更多
Let G = (V, E) be a graph and C<sub>m</sub> be the cycle graph with m vertices. In this paper, we continued Yeh’s work [1] on the distance labeling of the cycle graph Cm</sub>. An n-set distance lab...Let G = (V, E) be a graph and C<sub>m</sub> be the cycle graph with m vertices. In this paper, we continued Yeh’s work [1] on the distance labeling of the cycle graph Cm</sub>. An n-set distance labeling of a graph G is the labeling of the vertices (with n labels per vertex) of G under certain constraints depending on the distance between each pair of the vertices in G. Following Yeh’s notation [1], the smallest value for the largest label in an n-set distance labeling of G is denoted by λ<sub>1</sub><sup>(n)</sup>(G). Basic results were presented in [1] for λ1</sub>(2)</sup>(C<sub>m</sub>) for all m and λ1</sub>(n)</sup>(C<sub>m</sub>) for some m where n ≥ 3. However, there were still gaps left unstudied due to case-by-case complexities. For these uncovered cases, we proved a lower bound for λ1</sub>(n)</sup>(C<sub>m</sub>). Then we proposed an algorithm for finding an n-set distance labeling for n ≥ 3 based on our proof of the lower bound. We verified every single case for n = 3 up to n = 500 by this same algorithm, which indicated that the upper bound is the same as the lower bound for n ≤ 500.展开更多
针对传统编程作业批改效率偏低、主观性突出及现有自动化工具评测维度单一的现实问题,文章构建了融合大语言模型(Large Language Model,LLM)与抽象语法树(Abstract Syntax Tree,AST)的全维度评测系统。该系统借助AST解析提取代码结构特...针对传统编程作业批改效率偏低、主观性突出及现有自动化工具评测维度单一的现实问题,文章构建了融合大语言模型(Large Language Model,LLM)与抽象语法树(Abstract Syntax Tree,AST)的全维度评测系统。该系统借助AST解析提取代码结构特征,结合LLM的语义理解能力,对代码正确性、逻辑完备性及编程规范性进行多维度评估,同时引入知识图谱构建错因归溯与补救建议,依托指令工程生成个性化反馈内容。实验数据显示,该系统在函数题、类与对象题等典型题型中的综合评分准确率达89.1%,反馈有效性平均得分为4.05分,批改效率提升幅度达85%,可助力智能化教学实践。展开更多
基金supported by National Key Basic Research Program of China(973 program) under Grant No. 2007CB307101National Natural Science Foundation of China under Grant No.60833002,No.60802016,No.60972010+1 种基金Next Generation Internet of China under Grant No.CNGI-0903-05the Fundamental Research Funds for the Central Universities under Grant No.2009YJS011
文摘Wireless sensor networks are suffering from serious frequency interference.In this paper,we propose a channel assignment algorithm based on graph theory in wireless sensor networks.We first model the conflict infection graph for channel assignment with the goal of global optimization minimizing the total interferences in wireless sensor networks.The channel assignment problem is equivalent to the generalized graph-coloring problem which is a NP-complete problem.We further present a meta-heuristic Wireless Sensor Network Parallel Tabu Search(WSN-PTS) algorithm,which can optimize global networks with small numbers of iterations.The results from a simulation experiment reveal that the novel algorithm can effectively solve the channel assignment problem.
文摘To solve the deadlock problem of tasks that the interdependence between tasks fails to consider during the course of resource assignment and task scheduling based on the heuristics algorithm, an improved ant colony system （ACS） based algorithm is proposed. First, how to map the resource assignment and task scheduling （RATS） problem into the optimization selection problem of task resource assignment graph （TRAG） and to add the semaphore mechanism in the optimal TRAG to solve deadlocks are explained. Secondly, how to utilize the grid pheromone system model to realize the algorithm based on ACS is explicated. This refers to the construction of TRAG by the random selection of appropriate resources for each task by the user agent and the optimization of TRAG through the positive feedback and distributed parallel computing mechanism of the ACS. Simulation results show that the proposed algorithm is effective and efficient in solving the deadlock problem.
基金The National Natural Science Foundation of China(No.61741102,61471164,61601122)the Fundamental Research Funds for the Central Universities(No.SJLX_160040)
文摘In order to solve the problem of efficiently assigning tasks in an ad-hoc mobile cloud( AMC),a task assignment algorithm based on the heuristic algorithm is proposed. The proposed task assignment algorithm based on particle swarm optimization and simulated annealing( PSO-SA) transforms the dependencies between tasks into a directed acyclic graph( DAG) model. The number in each node represents the computation workload of each task and the number on each edge represents the workload produced by the transmission. In order to simulate the environment of task assignment in AMC,mathematical models are developed to describe the dependencies between tasks and the costs of each task are defined. PSO-SA is used to make the decision for task assignment and for minimizing the cost of all devices,which includes the energy consumption and time delay of all devices.PSO-SA also takes the advantage of both particle swarm optimization and simulated annealing by selecting an optimal solution with a certain probability to avoid falling into local optimal solution and to guarantee the convergence speed. The simulation results show that compared with other existing algorithms,the PSO-SA has a smaller cost and the result of PSO-SA can be very close to the optimal solution.
文摘An L（2, 1）-labeling of a graph G is a function f from the vertex set V（G） to the set of all nonnegative integers such that ｜f（x） - f（y）｜ 〉 2 if d（x, y） = 1 and ｜f（x）-f（y）｜ ≥ 1 ifd（x, y） = 2. The L（2, 1）-labeling number λ（G） of G is the smallest number k such that G has an L（2, 1）-labeling with max{f（v） ： v ∈ V（G）} = k. We study the L（3, 2, 1）-labeling which is a generalization of the L（2, 1）-labeling on the graph formed by the （Cartesian） product and composition of 3 graphs and derive the upper bounds of λ3（G） of the graph.
文摘Discusses how to assign a set of noninterference radio channels to a symmetric network of transmitter location over a large planar area, the minimum of the span and the assignment of the channels with the changing of minimum distance among the same channels and the changing of the minimum difference among the adjacent channels. The minimum interval in the frequency spectrum of 9 interger channels is proved and obtained by using the graphic theory and the reduction to absurdity on condition that interference from nearby transmitters is avoided in the whole given grid and the grid spreading arbitrarily far in all directions.
文摘Solving the absent assignment problem of the shortest time limit in a weighted bipartite graph with the minimal weighted k-matching algorithm is unsuitable for situations in which large numbers of problems need to be addressed by large numbers of parties. This paper simplifies the algorithm of searching for the even alternating path that contains a maximal element using the minimal weighted k-matching theorem and intercept graph. A program for solving the maximal efficiency assignment problem was compiled. As a case study, the program was used to solve the assignment problem of water piping repair in the case of a large number of companies and broken pipes, and the validity of the program was verified.
基金supported by National Natural Science Foundation of China (No.60774007) and the Royal Society of UK
文摘A variety of problems in digital circuits, computer networks, automated manufacturing plants, etc., can be modeled as min-max systems. The cycle time is an important performance metric of such systems. In this paper, we focus on the cycle time assignment of minimax systems which corresponds to the pole assignment problem in traditional linear control systems. For the min- max system with max-plus inputs and outputs, we show that the cycle time can be assigned disjointedly by a state feedback, if and only if the system is reachable. Furthermore, a necessary and sufficient condition for the cycle time to be assigned independently by a state feedback is given. The methods are constructive, and some numerical examples are given to illustrate how the methods work in practice.
文摘L (2, 1)-labeling number, λ(G( Z , D)) , of distance graph G( Z , D) is studied. For general finite distance set D , it is shown that 2D+2≤λ(G( Z , D))≤D 2+3D. Furthermore, λ(G( Z , D)) ≤8 when D consists of two prime positive odd integers is proved. Finally, a new concept to study the upper bounds of λ(G) for some special D is introduced. For these sets, the upper bound is improved to 7.
文摘The L(2,1)-labelling number of distance graphs G(D), denoted by λ(D), isstudied. It is shown that distance graphs satisfy λ(G) ≤Δ~2. Moreover, we prove λ({1,2, ..., k})=2k +2 and λ({1,3,..., 2k -1}) =2k + 2 for any fixed positive integer k. Suppose k, a ∈ N and k,a≥2. If k≥a, then λ({a, a + 1,..., a + k - 1}) = 2(a + k-1). Otherwise, λ({a, a + 1, ..., a + k- 1}) ≤min{2(a + k-1), 6k -2}. When D consists of two positive integers,6≤λ(D)≤8. For thespecial distance sets D = {k, k + 1}(any k ∈N), the upper bound of λ(D) is improved to 7.
文摘An L(0,1)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between the labels assigned to any two adjacent vertices is at least zero and the difference between the labels assigned to any two vertices which are at distance two is at least one. The span of an L(0,1)-labelling is the maximum label number assigned to any vertex of G. The L(0,1)-labelling number of a graph G, denoted by λ0.1(G) is the least integer k such that G has an L(0,1)-labelling of span k. This labelling has an application to a computer code assignment problem. The task is to assign integer control codes to a network of computer stations with distance restrictions. A cactus graph is a connected graph in which every block is either an edge or a cycle. In this paper, we label the vertices of a cactus graph by L(0,1)-labelling and have shown that, △-1≤λ0.1(G)≤△ for a cactus graph, where △ is the degree of the graph G.
基金The NSF (60673048) of China the NSF (KJ2009B002,KJ2009B237Z) of Education Ministry of Anhui Province.
文摘An L（3, 2, 1）-labeling of a graph G is a function from the vertex set V（G） to the set of all nonnegative integers such that ｜f（u）-f（v）｜≥3 if dG（u,v） = 1, ｜f（u）-f（v）｜≥2 if dG（u,v） = 2, and ｜f（u）-f（v）｜≥1 if dG（u,v） = 3. The L（3, 2,1）-labeling problem is to find the smallest number λ3（G） such that there exists an L（3, 2,1）-labeling function with no label greater than it. This paper studies the problem for bipartite graphs. We obtain some bounds of λ3 for bipartite graphs and its subclasses. Moreover, we provide a best possible condition for a tree T such that λ3（T） attains the minimum value.
文摘A k-L(2,1)-labeling for a graph G is a function such that whenever and whenever u and v are at distance two apart. The λ-number for G, denoted by λ(G), is the minimum k over all k-L(2,1)-labelings of G. In this paper, we show that for or 11, which confirms Conjecture 6.1 stated in [X. Li, V. Mak-Hau, S. Zhou, The L(2,1)-labelling problem for cubic Cayley graphs on dihedral groups, J. Comb. Optim. (2013) 25: 716-736] in the case when or 11. Moreover, we show that? if 1) either (mod 6), m is odd, r = 3, or 2) (mod 3), m is even (mod 2), r = 0.
文摘Let G = (V, E) be a graph and C<sub>m</sub> be the cycle graph with m vertices. In this paper, we continued Yeh’s work [1] on the distance labeling of the cycle graph Cm</sub>. An n-set distance labeling of a graph G is the labeling of the vertices (with n labels per vertex) of G under certain constraints depending on the distance between each pair of the vertices in G. Following Yeh’s notation [1], the smallest value for the largest label in an n-set distance labeling of G is denoted by λ<sub>1</sub><sup>(n)</sup>(G). Basic results were presented in [1] for λ1</sub>(2)</sup>(C<sub>m</sub>) for all m and λ1</sub>(n)</sup>(C<sub>m</sub>) for some m where n ≥ 3. However, there were still gaps left unstudied due to case-by-case complexities. For these uncovered cases, we proved a lower bound for λ1</sub>(n)</sup>(C<sub>m</sub>). Then we proposed an algorithm for finding an n-set distance labeling for n ≥ 3 based on our proof of the lower bound. We verified every single case for n = 3 up to n = 500 by this same algorithm, which indicated that the upper bound is the same as the lower bound for n ≤ 500.
文摘针对传统编程作业批改效率偏低、主观性突出及现有自动化工具评测维度单一的现实问题,文章构建了融合大语言模型(Large Language Model,LLM)与抽象语法树(Abstract Syntax Tree,AST)的全维度评测系统。该系统借助AST解析提取代码结构特征,结合LLM的语义理解能力,对代码正确性、逻辑完备性及编程规范性进行多维度评估,同时引入知识图谱构建错因归溯与补救建议,依托指令工程生成个性化反馈内容。实验数据显示,该系统在函数题、类与对象题等典型题型中的综合评分准确率达89.1%,反馈有效性平均得分为4.05分,批改效率提升幅度达85%,可助力智能化教学实践。
