graph coloring

(redirected from Coloring problem)

graph coloring

This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)
References in periodicals archive ?
In the following years, the combination of coloring problem and ternary code was examined by another group.
A graph coloring problem starts with a graph - a visual representation of a set of objects connected in some way.
To assign each train to a conflict-free route through the railway station in the tentative saturated timetable, there are two typical types of routing methods: one is to model the problem as a node packing problem and the other is to model the problem based on the graph coloring problem [3].
Hence, it is needed to minimize multiple conflicting cost functions, which can be best solved through the method of multiobjective optimization [15] that imported several features from the research on the graph coloring problem and used a variable-length chromosome representation that this paper also adopts.
The ant colony algorithm, which is a bionic algorithm, is applied herein to the study of the three regular graph coloring problem, in order to gain a more reasonable solution to the problems of coloring and number labeling.
The list coloring problem is NP-complete for perfect graphs and planar graphs (see [7]).
The search for an ideal blockmodel can usually be formulated as a graph coloring problem. By our classification, we show that the practical approaches can be seen as methods to optimize very specific relaxations of these problems.
Theorem 11 The EQUITABLE COLORING problem can be solved in time [absolute value of V] [absolute value of E]r x [2.sup.O(kxlog k)] on graphs oftwin-cover at most k.
The problem of reducing the signal interference and collision is represented as a graph coloring problem. Adjacent edges in the graph are assigned different colors and different channels will be allocated from 1 to 11.
Yang et al., "An unenumerative DNA computing model for vertex coloring problem," IEEE Transactions on Nanobioscience, vol.
[1] Di-Francesco, P.: Folding and coloring problem in mathematics and physics, Bulletin of the American Mathematics Society, 37 (2000), 251-307
While boosting the colorant level until color consistency is achieved is one to way fix a coloring problem, there is no precise way to determine how much extra colorant is really needed to make the difference.