The biggest bottleneck in DNA computing is exponential explosion, in which the DNA molecules used as data in information processing grow exponentially with an increase of problem size. To overcome this bottleneck and ...The biggest bottleneck in DNA computing is exponential explosion, in which the DNA molecules used as data in information processing grow exponentially with an increase of problem size. To overcome this bottleneck and improve the processing speed, we propose a DNA computing model to solve the graph vertex coloring problem. The main points of the model are as follows： The exponential explosion prob- lem is solved by dividing subgraphs, reducing the vertex colors without losing the solutions, and ordering the vertices in subgraphs; and the bio-operation times are reduced considerably by a designed parallel polymerase chain reaction （PCR） technology that dramatically improves the processing speed. In this arti- cle, a 3-colorable graph with 61 vertices is used to illustrate the capability of the DNA computing model. The experiment showed that not only are all the solutions of the graph found, but also more than 99% of false solutions are deleted when the initial solution space is constructed. The powerful computational capability of the model was based on specific reactions among the large number of nanoscale oligonu- cleotide strands. All these tiny strands are operated by DNA self-assembly and parallel PCR. After thou- sands of accurate PCR operations, the solutions were found by recognizing, splicing, and assembling. We also prove that the searching capability of this model is up to 0（3^59）. By means of an exhaustive search, it would take more than 896 000 years for an electronic computer （5 x 10^14 s-1） to achieve this enormous task. This searching capability is the largest among both the electronic and non-electronic computers that have been developed since the DNA computing model was proposed by Adleman＇s research group in 2002 （with a searching capability of 0（2^20））.展开更多
For solving the map-coloring problems,this paper presents an energy function,amore effective dynamic equation and a more simple convergence condition.For the first time westudy the map-coloring problems in the way of ...For solving the map-coloring problems,this paper presents an energy function,amore effective dynamic equation and a more simple convergence condition.For the first time westudy the map-coloring problems in the way of connecting discrete Hopfield neural network withthe orthogonal optimization,and as a practical example,a color map of China is given.展开更多
In this paper, we consider the socalled k-coloring problem in general case.Firstly, a special quadratic 0-1 programming is constructed to formulate k-coloring problem. Secondly, by use of the equivalence between above...In this paper, we consider the socalled k-coloring problem in general case.Firstly, a special quadratic 0-1 programming is constructed to formulate k-coloring problem. Secondly, by use of the equivalence between above quadratic0-1 programming and its relaxed problem, k-coloring problem is converted intoa class of (continuous) nonconvex quadratic programs, and several theoreticresults are also introduced. Thirdly, linear programming approximate algorithmis quoted and verified for this class of nonconvex quadratic programs. Finally,examining problems which are used to test the algorithm are constructed andsufficient computation experiments are reported.展开更多
To solve the resource-constrained multiple project scheduling problem(RCMPSP) more effectively,a method based on timed colored Petri net(TCPN) was proposed.In this methodology,firstly a novel mapping mechanism between...To solve the resource-constrained multiple project scheduling problem(RCMPSP) more effectively,a method based on timed colored Petri net(TCPN) was proposed.In this methodology,firstly a novel mapping mechanism between traditional network diagram such as CPM(critical path method)/PERT(program evaluation and review technique) and TCPN was presented.Then a primary TCPN(PTCPN) for solving RCMPSP was modeled based on the proposed mapping mechanism.Meanwhile,the object PTCPN was used to simulate the multiple projects scheduling and to find the approximately optimal value of RCMPSP.Finally,the performance of the proposed approach for solving RCMPSP was validated by executing a mould manufacturing example.展开更多
An evolutionary network driven by dynamics is studied and applied to the graph coloring problem. From an initial structure, both the topology and the coupling weights evolve according to the dynamics. On the other han...An evolutionary network driven by dynamics is studied and applied to the graph coloring problem. From an initial structure, both the topology and the coupling weights evolve according to the dynamics. On the other hand, the dynamics of the network are determined by the topology and the coupling weights, so an interesting structure-dynamics co-evolutionary scheme appears. By providing two evolutionary strategies, a network described by the complement of a graph will evolve into several clusters of nodes according to their dynamics. The nodes in each cluster can be assigned the same color and nodes in different clusters assigned different colors. In this way, a co-evolution phenomenon is applied to the graph coloring problem. The proposed scheme is tested on several benchmark graphs for graph coloring.展开更多
Coloring the nodes of a graph is a commonly used technique to speed up clique search algorithms. Coloring the edges of the graph as a preconditioning method can also be used to speed up computations. In this paper we ...Coloring the nodes of a graph is a commonly used technique to speed up clique search algorithms. Coloring the edges of the graph as a preconditioning method can also be used to speed up computations. In this paper we will show that an unconventional coloring scheme of the edges leads to an NP-complete problem when one intends to determine the optimal number of colors.展开更多
Let C be a set of colors, and let ?be an integer cost assigned to a color c in C. An edge-coloring of a graph ?is assigning a color in C to each edge ?so that any two edges having end-vertex in common have different c...Let C be a set of colors, and let ?be an integer cost assigned to a color c in C. An edge-coloring of a graph ?is assigning a color in C to each edge ?so that any two edges having end-vertex in common have different colors. The cost ?of an edge-coloring f of G is the sum of costs ?of colors ?assigned to all edges e in G. An edge-coloring f of G is optimal if ?is minimum among all edge-colorings of G. A cactus is a connected graph in which every block is either an edge or a cycle. In this paper, we give an algorithm to find an optimal edge- ??coloring of a cactus in polynomial time. In our best knowledge, this is the first polynomial-time algorithm to find an optimal edge-coloring of a cactus.展开更多
Visual information about an object is widely distributed over the cortex. The problem of how this information gets reassembled in consciousness is the “binding problem”. It is assumed in this paper that consciousnes...Visual information about an object is widely distributed over the cortex. The problem of how this information gets reassembled in consciousness is the “binding problem”. It is assumed in this paper that consciousness reads the distributed information as a laser reads a barcode;and that this solves the binding problem without resorting to oscillations, or synchronous signals, or any other form of mechanical association. Cortical distributions are made intelligible by consciousness that learns from childhood to recognize cortical arrays of single objects and project them onto the external world. An example shows how consciousness exercises its influence in the case of a well-known line drawing. When an object is constructed by consciousness there is no guarantee that the resulting image will be anything like the original object of observation. However, there is reason to believe that most of the visual images of our surroundings reflect real properties of those surroundings. These images have a constancy about them that is not always conveyed by the sensory input, but consistency in the external world can be learned by consciousness that is able to override the incongruities of the senses.展开更多
Scheduling sports leagues has drawn significant attention to itself in recent years, as it involves considerable revenue as well as challenging combinatorial optimization problems. A particular class of these problems...Scheduling sports leagues has drawn significant attention to itself in recent years, as it involves considerable revenue as well as challenging combinatorial optimization problems. A particular class of these problems is the Traveling Tournament Problem (TTP) which focuses on minimizing the total traveling distance for teams. In this paper, an efficient simulated annealing approach is presented for TTP which applies two simultaneous and disparate models for the problem in order to search the solutions space more effectively. Also, a computationally efficient modified greedy scheme is proposed for constructing a favorable initial solution for the simulated annealing algorithm. Our computational experiments, carried out on standard instances, demonstrate that this approach competes with previous offered methods in quality of found solutions and their computational time.展开更多
A new 3D surface contouring and ranging system based on digital fringe projection and phase shifting technique is presented.Using the phase-shift technique,points cloud with high spatial resolution and limited accurac...A new 3D surface contouring and ranging system based on digital fringe projection and phase shifting technique is presented.Using the phase-shift technique,points cloud with high spatial resolution and limited accuracy can be generated.Stereo-pair images obtained from two cameras can be used to compute 3D world coordinates of a point using traditional active triangulation approach,yet the camera calibration is crucial.Neural network is a well-known approach to approximate a nonlinear system without an explicit physical model,in this work it is used to train the stereo vision application system to calculating 3D world coordinates such that the camera calibration can be bypassed.The training set for neural network consists of a variety of stereo-pair images and the corresponding 3D world coordinates.The picture elements correspondence problem is solved by using projected color-coded fringes with different orientations.Color imbalance is completely eliminated by the new color-coded method.Once the high accuracy correspondence of 2D images with 3D points is acquired,high precision 3D points cloud can be recognized by the well trained net.The obvious advantage of this approach is that high spatial resolution can be obtained by the phase-shifting technique and high accuracy 3D object point coordinates are achieved by the well trained net which is independent of the camera model works for any type of camera.Some experiments verified the performance of the method.展开更多
A proper k-total coloring f of the graph G（V, E） is said to be a k-vertex strong total coloring if and only if for every v ∈ V（G）, the elements in N[v] are colored with different colors, where N[v] =. {u｜uv E V...A proper k-total coloring f of the graph G（V, E） is said to be a k-vertex strong total coloring if and only if for every v ∈ V（G）, the elements in N[v] are colored with different colors, where N[v] =. {u｜uv E V（G）} ∪{v}. The value xT^vs（G） = min{k｜ there is a k-vertex strong total coloring of G} is called the vertex strong total chromatic number of G. For a 3-connected plane graph G（V, E）, if the graph obtained from G（V, E） by deleting all the edges on the boundary of a face f0 is a tree, then G（V, E） is called a Halin-graph. In this paper, xT^vs,8（G） of the Halin-graph G（V,E） with A（G） 〉 6 and some special graphs are obtained. Furthermore, a conjecture is initialized as follows： Let G（V, E） be a graph with the order of each component are at least 6, then xT^vs（G） ≤ △（G） ＋ 2, where A（G） is the maximum degree of G.展开更多
基金The authors are grateful for the support from the National Natural Science Foundation of China （61632002, 61379059, and 61572046）.
文摘The biggest bottleneck in DNA computing is exponential explosion, in which the DNA molecules used as data in information processing grow exponentially with an increase of problem size. To overcome this bottleneck and improve the processing speed, we propose a DNA computing model to solve the graph vertex coloring problem. The main points of the model are as follows： The exponential explosion prob- lem is solved by dividing subgraphs, reducing the vertex colors without losing the solutions, and ordering the vertices in subgraphs; and the bio-operation times are reduced considerably by a designed parallel polymerase chain reaction （PCR） technology that dramatically improves the processing speed. In this arti- cle, a 3-colorable graph with 61 vertices is used to illustrate the capability of the DNA computing model. The experiment showed that not only are all the solutions of the graph found, but also more than 99% of false solutions are deleted when the initial solution space is constructed. The powerful computational capability of the model was based on specific reactions among the large number of nanoscale oligonu- cleotide strands. All these tiny strands are operated by DNA self-assembly and parallel PCR. After thou- sands of accurate PCR operations, the solutions were found by recognizing, splicing, and assembling. We also prove that the searching capability of this model is up to 0（3^59）. By means of an exhaustive search, it would take more than 896 000 years for an electronic computer （5 x 10^14 s-1） to achieve this enormous task. This searching capability is the largest among both the electronic and non-electronic computers that have been developed since the DNA computing model was proposed by Adleman＇s research group in 2002 （with a searching capability of 0（2^20））.
文摘For solving the map-coloring problems,this paper presents an energy function,amore effective dynamic equation and a more simple convergence condition.For the first time westudy the map-coloring problems in the way of connecting discrete Hopfield neural network withthe orthogonal optimization,and as a practical example,a color map of China is given.
文摘In this paper, we consider the socalled k-coloring problem in general case.Firstly, a special quadratic 0-1 programming is constructed to formulate k-coloring problem. Secondly, by use of the equivalence between above quadratic0-1 programming and its relaxed problem, k-coloring problem is converted intoa class of (continuous) nonconvex quadratic programs, and several theoreticresults are also introduced. Thirdly, linear programming approximate algorithmis quoted and verified for this class of nonconvex quadratic programs. Finally,examining problems which are used to test the algorithm are constructed andsufficient computation experiments are reported.
文摘To solve the resource-constrained multiple project scheduling problem(RCMPSP) more effectively,a method based on timed colored Petri net(TCPN) was proposed.In this methodology,firstly a novel mapping mechanism between traditional network diagram such as CPM(critical path method)/PERT(program evaluation and review technique) and TCPN was presented.Then a primary TCPN(PTCPN) for solving RCMPSP was modeled based on the proposed mapping mechanism.Meanwhile,the object PTCPN was used to simulate the multiple projects scheduling and to find the approximately optimal value of RCMPSP.Finally,the performance of the proposed approach for solving RCMPSP was validated by executing a mould manufacturing example.
基金supported by the National Natural Science Foundation of China (Grants Nos. 61072139,61072106,61203303,61003198,61272279,and 61003199)
文摘An evolutionary network driven by dynamics is studied and applied to the graph coloring problem. From an initial structure, both the topology and the coupling weights evolve according to the dynamics. On the other hand, the dynamics of the network are determined by the topology and the coupling weights, so an interesting structure-dynamics co-evolutionary scheme appears. By providing two evolutionary strategies, a network described by the complement of a graph will evolve into several clusters of nodes according to their dynamics. The nodes in each cluster can be assigned the same color and nodes in different clusters assigned different colors. In this way, a co-evolution phenomenon is applied to the graph coloring problem. The proposed scheme is tested on several benchmark graphs for graph coloring.
文摘Coloring the nodes of a graph is a commonly used technique to speed up clique search algorithms. Coloring the edges of the graph as a preconditioning method can also be used to speed up computations. In this paper we will show that an unconventional coloring scheme of the edges leads to an NP-complete problem when one intends to determine the optimal number of colors.
文摘Let C be a set of colors, and let ?be an integer cost assigned to a color c in C. An edge-coloring of a graph ?is assigning a color in C to each edge ?so that any two edges having end-vertex in common have different colors. The cost ?of an edge-coloring f of G is the sum of costs ?of colors ?assigned to all edges e in G. An edge-coloring f of G is optimal if ?is minimum among all edge-colorings of G. A cactus is a connected graph in which every block is either an edge or a cycle. In this paper, we give an algorithm to find an optimal edge- ??coloring of a cactus in polynomial time. In our best knowledge, this is the first polynomial-time algorithm to find an optimal edge-coloring of a cactus.
文摘Visual information about an object is widely distributed over the cortex. The problem of how this information gets reassembled in consciousness is the “binding problem”. It is assumed in this paper that consciousness reads the distributed information as a laser reads a barcode;and that this solves the binding problem without resorting to oscillations, or synchronous signals, or any other form of mechanical association. Cortical distributions are made intelligible by consciousness that learns from childhood to recognize cortical arrays of single objects and project them onto the external world. An example shows how consciousness exercises its influence in the case of a well-known line drawing. When an object is constructed by consciousness there is no guarantee that the resulting image will be anything like the original object of observation. However, there is reason to believe that most of the visual images of our surroundings reflect real properties of those surroundings. These images have a constancy about them that is not always conveyed by the sensory input, but consistency in the external world can be learned by consciousness that is able to override the incongruities of the senses.
文摘Scheduling sports leagues has drawn significant attention to itself in recent years, as it involves considerable revenue as well as challenging combinatorial optimization problems. A particular class of these problems is the Traveling Tournament Problem (TTP) which focuses on minimizing the total traveling distance for teams. In this paper, an efficient simulated annealing approach is presented for TTP which applies two simultaneous and disparate models for the problem in order to search the solutions space more effectively. Also, a computationally efficient modified greedy scheme is proposed for constructing a favorable initial solution for the simulated annealing algorithm. Our computational experiments, carried out on standard instances, demonstrate that this approach competes with previous offered methods in quality of found solutions and their computational time.
基金Supported by the Eleventh Five-Year Pre-research Project of China.
文摘A new 3D surface contouring and ranging system based on digital fringe projection and phase shifting technique is presented.Using the phase-shift technique,points cloud with high spatial resolution and limited accuracy can be generated.Stereo-pair images obtained from two cameras can be used to compute 3D world coordinates of a point using traditional active triangulation approach,yet the camera calibration is crucial.Neural network is a well-known approach to approximate a nonlinear system without an explicit physical model,in this work it is used to train the stereo vision application system to calculating 3D world coordinates such that the camera calibration can be bypassed.The training set for neural network consists of a variety of stereo-pair images and the corresponding 3D world coordinates.The picture elements correspondence problem is solved by using projected color-coded fringes with different orientations.Color imbalance is completely eliminated by the new color-coded method.Once the high accuracy correspondence of 2D images with 3D points is acquired,high precision 3D points cloud can be recognized by the well trained net.The obvious advantage of this approach is that high spatial resolution can be obtained by the phase-shifting technique and high accuracy 3D object point coordinates are achieved by the well trained net which is independent of the camera model works for any type of camera.Some experiments verified the performance of the method.
文摘最小负载着色问题(minimum load coloring problem,MLCP)源于构建光通信网络的波分复用(wavelength division multiplexing,WDM)技术,是一个被证明的NP完全问题.由于NP完全问题有着随问题规模呈指数增长的解空间,因此启发式算法常被用来解决这类问题.在对国内外相关工作的深入分析基础上得知,现有的多类求解MLCP问题的启发式算法中局部搜索算法表现是最好的.研究针对当前求解MLCP问题的局部搜索算法在数据预处理和邻域空间搜索上的不足,提出了两点相应的优化策略:一是在数据的预处理阶段,提出一度顶点规则来约简数据的规模,进而减小MLCP问题的搜索空间;二是在算法的邻域空间搜索阶段,提出两阶段多重选择策略(twostage best from multiple selections,TSBMS)来帮助局部搜索算法在面对不同规模的邻域空间时可以高效地选择一个高质量的邻居解,它有效地提高了局部搜索算法在处理不同规模数据时的求解表现.将这个优化后的局部搜索算法命名为IRLTS.采用74个经典的测试用例来验证IRLTS算法的有效性.实验结果表明,无论最优解还是平均解,IRLTS算法在大多数测试用例上都明显优于当前表现最好的3个局部搜索算法.此外,还通过实验验证了所提策略的有效性以及分析了关键参数对算法的影响.
基金the National Natural Science Foundation of China (No.19871036) the Qinglan talent Funds of Lanzhou Jiaotong University
文摘A proper k-total coloring f of the graph G（V, E） is said to be a k-vertex strong total coloring if and only if for every v ∈ V（G）, the elements in N[v] are colored with different colors, where N[v] =. {u｜uv E V（G）} ∪{v}. The value xT^vs（G） = min{k｜ there is a k-vertex strong total coloring of G} is called the vertex strong total chromatic number of G. For a 3-connected plane graph G（V, E）, if the graph obtained from G（V, E） by deleting all the edges on the boundary of a face f0 is a tree, then G（V, E） is called a Halin-graph. In this paper, xT^vs,8（G） of the Halin-graph G（V,E） with A（G） 〉 6 and some special graphs are obtained. Furthermore, a conjecture is initialized as follows： Let G（V, E） be a graph with the order of each component are at least 6, then xT^vs（G） ≤ △（G） ＋ 2, where A（G） is the maximum degree of G.
