Heuristics for rapidly four-coloring large planar graphs
Heuristics for rapidly four-coloring large planar graphs
复制标题
快速四色大型平面图的启发式方法
作者：
Craig A. Morgenstern;H. Shapiro
我们提出了几种快速四色大型平面图的算法，并讨论了来自两类不同的随机生成实例的140多个图的广泛实验结果，这些实例具有多达128,000个顶点。虽然算法可能需要指数时间，但我们更复杂的算法的观察运行时间与测试的大小范围内的顶点数量呈线性关系。结合使用Kempe链和回溯以及快速启发式算法(通常但不总是解决僵局)，我们可以使用混合算法：(1)成功地将我们所有的测试图四色，(2)在实际运行中，平均只比著名的、不精确的、代码简单的Brélaz的Θ(N)饱和算法慢一倍。
We present several algorithms for rapidly four-coloring large planar graphs and discuss the results of extensive experimentation with over 140 graphs from two distinct classes of randomly generated instances having up to 128,000 vertices. Although the algorithms can potentially require exponential time, the observed running times of our more sophisticated algorithms are linear in the number of vertices over the range of sizes tested. The use of Kempe chaining and backtracking together with a fast heuristic which usually, but not always, resolves impasses gives us hybrid algorithms that: (1) successfully four-color all our test graphs, and (2) in practice run, on average, only twice as slow as the well-known, nonexact, simple to code, Θ(n) saturation algorithm of Brélaz.