Parallel Heuristics for Improved, Balanced Graph Colorings
✍ Scribed by Robert K. Gjertsen; Jr.; Mark T. Jones; Paul E. Plassmann
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 399 KB
- Volume
- 37
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
The computation of good, balanced graph colorings is an essential part of many algorithms required in scientific and engineering applications. Motivated by an effective sequential heuristic, we introduce a new parallel heuristic, PLF, and show that this heuristic has the same expected runtime under the PRAM computational model as the scalable coloring heuristic introduced by Jones and Plassmann. We present experimental results performed on the Intel DELTA that demonstrate that this new heuristic consistently generates better colorings and requires only slightly more time than the JP heuristic. In the second part of the paper we introduce two new parallel colorbalancing heuristics, PDR(k) and PLF(k). We show that these heuristics have the desirable property that they do not increase the number of colors used by an initial coloring during the balancing process. We present experimental results that show that these heuristics are very effective in obtaining balanced colorings and, in addition, exhibit scalable performance.