Title: Out-of-Core Graph Coloring Algorithm
Speaker: Yiqian Liu
Advisor: Martin Burtscher
When: Friday, July 3 @ 9:30 AM
Where: https://txstate.zoom.us/j/3818836279 (no password needed)
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 my implementation, but FirstFit is four times faster whereas Boost is six times slower.
Deadline: July 6, 2020, midnight