Heuristics for rapidly four-coloring large planar graphs |
| |
Authors: | Craig A Morgenstern and Henry D Shapiro |
| |
Affiliation: | (1) Department of Computer Science, Texas Christian University, 76129 Fort Worth, TX, USA;(2) Department of Computer Science, University of New Mexico, 87131 Albuquerque, NM, USA |
| |
Abstract: | 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. |
| |
Keywords: | Four coloring Planar graphs Kempe chaining Saturation algorithm of Bré laz Heuristic algorithms |
本文献已被 SpringerLink 等数据库收录! |
|