A channel allocation algorithm based on the maximum independent set is proposed to decrease network conflict and improve network performance. First, a channel allocation model is formulated and a series of the maximum...A channel allocation algorithm based on the maximum independent set is proposed to decrease network conflict and improve network performance. First, a channel allocation model is formulated and a series of the maximum independent sets （MISs） are obtained from a contention graph by the proposed approximation algorithm with low complexity. Then, a weighted contention graph is obtained using the number of contention vertices between two MISs as a weighted value. Links are allocated to channels by the weighted contention graph to minimize conflicts between independent sets. Finally, after channel allocation, each node allocates network interface cards （NICs） to links that are allocated channels according to the queue lengths of NICs. Simulations are conducted to evaluate the proposed algorithm. The results show that the proposed algorithm significantly improves the network throughput and decreases the end to end delay.展开更多
genetic algorithm is proposed for maximum independent set problems. A specially designed mutation operato is adopted to search the solution space more efficienily, where adjacen relation of a graph is inte-grated. The...genetic algorithm is proposed for maximum independent set problems. A specially designed mutation operato is adopted to search the solution space more efficienily, where adjacen relation of a graph is inte-grated. The DIMACS benchmark graphs are used to test our algorithm, and the results show that the algorithm outper-forms our previous version. Moreover two new low bounds are found for graphs in DIMACS.展开更多
A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vert...A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vertex set of a 3-regular simple graph is provided.展开更多
The paper discusses an enhancement to a recently presented supervised learning algorithm to solve the Maximum Independent Set problem.In particular,it is shown that the algorithm can be improved by simplifying the tas...The paper discusses an enhancement to a recently presented supervised learning algorithm to solve the Maximum Independent Set problem.In particular,it is shown that the algorithm can be improved by simplifying the task learnt by the neural network adopted,with measurable effects on the quality of the solutions provided on unseen instances.Empirical results are presented to validate the idea..展开更多
Win proved a well-known result that the graph G of connectivity κ(G) withα(G) ≤κ(G) + k-1(k ≥ 2) has a spanning k-ended tree, i.e., a spanning tree with at most k leaves. In this paper, the authors extended the W...Win proved a well-known result that the graph G of connectivity κ(G) withα(G) ≤κ(G) + k-1(k ≥ 2) has a spanning k-ended tree, i.e., a spanning tree with at most k leaves. In this paper, the authors extended the Win theorem in case when κ(G) = 1 to the following: Let G be a simple connected graph of order large enough such that α(G) ≤ k + 1(k ≥ 3) and such that the number of maximum independent sets of cardinality k + 1 is at most n-2k-2. Then G has a spanning k-ended tree.展开更多
A subset I of vertices of an undirected connected graph G is a nonseparating independent set(NSIS)if no two vertices of I are adjacent and GI is connected.Let Z(G)denote the cardinality of a maximum NSIS of G.A nonsep...A subset I of vertices of an undirected connected graph G is a nonseparating independent set(NSIS)if no two vertices of I are adjacent and GI is connected.Let Z(G)denote the cardinality of a maximum NSIS of G.A nonseparating independent set containing Z(G)vertices is called the maximum nonseparating independent set.In this paper,we firstly give an upper bound for Z(G)of regular graphs and determine Z(G)for some types of circular graphs.Secondly,we show a relationship between Z(G)and the maximum genus M(G)of a general graph.Finally,an important formula is provided to compute Z(G),i.e.,Z(G)=Σx∈I dI(x)+2(M(G-I)-γM(G))+(ξ(G-I)-ξ(G));where I is the maximum nonseparating independent set and ξ(G)is the Betti deficiency(Xuong,1979)of G.展开更多
The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with...The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a graph.No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale.However,several algorithms are proposed that solve the problem approximately in a short polynomial time scale.Such algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational resources.The MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising etc.This work aims to solve the MVCP approximately by a novel graph decomposition approach.The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths.In order to reduce complexity of the algorithm a new strategy is also proposed.The reduction strategy can be used for any algorithm solving MVCP.Based on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the MVCP.These algorithms are tested using well known standard benchmark graphs.The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.展开更多
基金The National High Technology Research and Development Program of China(863 Program)(No.2013AA013601)Prospective Research Project on Future Netw orks of Jiangsu Future Netw orks Innovation Institute(No.BY2013095-1-18)
文摘A channel allocation algorithm based on the maximum independent set is proposed to decrease network conflict and improve network performance. First, a channel allocation model is formulated and a series of the maximum independent sets （MISs） are obtained from a contention graph by the proposed approximation algorithm with low complexity. Then, a weighted contention graph is obtained using the number of contention vertices between two MISs as a weighted value. Links are allocated to channels by the weighted contention graph to minimize conflicts between independent sets. Finally, after channel allocation, each node allocates network interface cards （NICs） to links that are allocated channels according to the queue lengths of NICs. Simulations are conducted to evaluate the proposed algorithm. The results show that the proposed algorithm significantly improves the network throughput and decreases the end to end delay.
文摘genetic algorithm is proposed for maximum independent set problems. A specially designed mutation operato is adopted to search the solution space more efficienily, where adjacen relation of a graph is inte-grated. The DIMACS benchmark graphs are used to test our algorithm, and the results show that the algorithm outper-forms our previous version. Moreover two new low bounds are found for graphs in DIMACS.
文摘A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vertex set of a 3-regular simple graph is provided.
基金supported by the Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung(CH)(No.200020-182360)。
文摘The paper discusses an enhancement to a recently presented supervised learning algorithm to solve the Maximum Independent Set problem.In particular,it is shown that the algorithm can be improved by simplifying the task learnt by the neural network adopted,with measurable effects on the quality of the solutions provided on unseen instances.Empirical results are presented to validate the idea..
基金supported by the National Natural Science Foundation of China(Nos.11871099,11671037,11801296)the Nature Science Foundation from Qinghai Province(No.2017-ZJ-949Q)
文摘Win proved a well-known result that the graph G of connectivity κ(G) withα(G) ≤κ(G) + k-1(k ≥ 2) has a spanning k-ended tree, i.e., a spanning tree with at most k leaves. In this paper, the authors extended the Win theorem in case when κ(G) = 1 to the following: Let G be a simple connected graph of order large enough such that α(G) ≤ k + 1(k ≥ 3) and such that the number of maximum independent sets of cardinality k + 1 is at most n-2k-2. Then G has a spanning k-ended tree.
基金supported by the National Natural Science Foundation of China(Nos.11171114,11401576,61662066,62072296)Science and Technology Commission of Shanghai Municipality(No.13dz2260400)。
文摘A subset I of vertices of an undirected connected graph G is a nonseparating independent set(NSIS)if no two vertices of I are adjacent and GI is connected.Let Z(G)denote the cardinality of a maximum NSIS of G.A nonseparating independent set containing Z(G)vertices is called the maximum nonseparating independent set.In this paper,we firstly give an upper bound for Z(G)of regular graphs and determine Z(G)for some types of circular graphs.Secondly,we show a relationship between Z(G)and the maximum genus M(G)of a general graph.Finally,an important formula is provided to compute Z(G),i.e.,Z(G)=Σx∈I dI(x)+2(M(G-I)-γM(G))+(ξ(G-I)-ξ(G));where I is the maximum nonseparating independent set and ξ(G)is the Betti deficiency(Xuong,1979)of G.
文摘The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a graph.No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale.However,several algorithms are proposed that solve the problem approximately in a short polynomial time scale.Such algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational resources.The MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising etc.This work aims to solve the MVCP approximately by a novel graph decomposition approach.The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths.In order to reduce complexity of the algorithm a new strategy is also proposed.The reduction strategy can be used for any algorithm solving MVCP.Based on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the MVCP.These algorithms are tested using well known standard benchmark graphs.The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.
