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.展开更多
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.展开更多
An incidence of a graph G is a vertex-edge pair(v,e)such that v is incidence with e.A conflict-free incidence coloring of a graph is a coloring of the incidences in such a way that two incidences(u,e)and(v,f)get disti...An incidence of a graph G is a vertex-edge pair(v,e)such that v is incidence with e.A conflict-free incidence coloring of a graph is a coloring of the incidences in such a way that two incidences(u,e)and(v,f)get distinct colors if and only if they conflict each other,i.e.,(i)u=v,(ii)uv is e or f,or(iii)there is a vertex w such that uw=e and vw=f.The minimum number of colors used among all conflict-free incidence colorings of a graph is the conflict-free incidence chromatic number.A graph is outer-1-planar if it can be drawn in the plane so that vertices are on the outer-boundary and each edge is crossed at most once.In this paper,we show that the conflict-free incidence chromatic number of an outer-1-planar graph with maximum degree△is either 2△or 2△+1 unless the graph is a cycle on three vertices,and moreover,all outer-1-planar graphs with conflict-free incidence chromatic number 2△or 2△+1 are completely characterized.An efficient algorithm for constructing an optimal conflict-free incidence coloring of a connected outer-1-planar graph is given.展开更多
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 accur...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.展开更多
基金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.
基金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.
基金supported by the Research Funds for the Central Universities(No.QTZX22053)the National Natural Science Foundation of China(No.11871055)。
文摘An incidence of a graph G is a vertex-edge pair(v,e)such that v is incidence with e.A conflict-free incidence coloring of a graph is a coloring of the incidences in such a way that two incidences(u,e)and(v,f)get distinct colors if and only if they conflict each other,i.e.,(i)u=v,(ii)uv is e or f,or(iii)there is a vertex w such that uw=e and vw=f.The minimum number of colors used among all conflict-free incidence colorings of a graph is the conflict-free incidence chromatic number.A graph is outer-1-planar if it can be drawn in the plane so that vertices are on the outer-boundary and each edge is crossed at most once.In this paper,we show that the conflict-free incidence chromatic number of an outer-1-planar graph with maximum degree△is either 2△or 2△+1 unless the graph is a cycle on three vertices,and moreover,all outer-1-planar graphs with conflict-free incidence chromatic number 2△or 2△+1 are completely characterized.An efficient algorithm for constructing an optimal conflict-free incidence coloring of a connected outer-1-planar graph is given.
文摘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.
