Kempe链的研究与民航空域频率覆盖重构

本文给出了构建Kempe链的算法,用Kempe链方法证明了Heawood反例是四色的,探讨了基于Kempe链模型的民航空域频率覆盖重构的可能性。     

Heuristics for rapidly four-coloring large planar graphs

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.The work of H. D. Shapiro was performed in part while he was on sabbatical at the Graz University of Technology.     

Automated generation of Kempe linkage and its complexity

It is a famous result of Kempe that a linkage can be designed to generate any given plane algebraic curve.In this paper,Kempe‘s result is improved to give a precise algorithm for generating Kempe linkage.We proved that for an algebraic plane curve of degrenn n,Kempe linkage uses at most O(n^4) links.Efforts to implement a program which may generate Kempe linkage and simulation of the generation process of the plane curves are presented in the paper.