Out-of-Core Graph Coloring Algorithm
Date
2020-08
Authors
Liu, Yiqian
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Out-of-core algorithms can process data sets that are too large to fit entirely into the
computer’s main memory. This thesis develops an out-of-core algorithm for graph coloring. It dynamically partitions the graph into subgraphs, processes them in sequence, and
records the color information needed by later subgraphs in a dense format. The algorithm
is guaranteed to produce the same coloring as the first-fit in-core algorithm. It employs
a new method to compactly record information and automatically resizes the associated
data structure to save memory. As there are no pre-existing out-of-core graph coloring
codes, the implementation can only be compared to leading in-core graph coloring codes.
Based on the geometric mean over 18 graphs from various domains, JP-D1 is 25% faster
and uses 13% fewer colors. FirstFit and Boost both use the same number of colors as the
presented implementation, but FirstFit is 4 times faster whereas Boost is 6 times slower.
Description
Keywords
Out-of-core algorithm, Graph coloring
Citation
Liu, Y. (2020). <i>Out-of-core graph coloring algorithm</i> (Unpublished thesis). Texas State University, San Marcos, Texas.