Out-of-Core Graph Coloring Algorithm
dc.contributor.advisor | Burtscher, Martin | |
dc.contributor.author | Liu, Yiqian | |
dc.contributor.committeeMember | Gu, Qijun | |
dc.contributor.committeeMember | Islam, Tanzima | |
dc.date.accessioned | 2020-07-30T21:37:55Z | |
dc.date.available | 2020-07-30T21:37:55Z | |
dc.date.issued | 2020-08 | |
dc.description.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. | |
dc.description.department | Computer Science | |
dc.format | Text | |
dc.format.extent | 55 pages | |
dc.format.medium | 1 file (.pdf) | |
dc.identifier.citation | Liu, Y. (2020). Out-of-core graph coloring algorithm (Unpublished thesis). Texas State University, San Marcos, Texas. | |
dc.identifier.uri | https://hdl.handle.net/10877/12256 | |
dc.language.iso | en | |
dc.subject | out-of-core algorithm | |
dc.subject | graph coloring | |
dc.title | Out-of-Core Graph Coloring Algorithm | |
dc.type | Thesis | |
thesis.degree.department | Computer Science | |
thesis.degree.discipline | Computer Science | |
thesis.degree.grantor | Texas State University | |
thesis.degree.level | Masters | |
thesis.degree.name | Master of Science |
Files
Original bundle
1 - 1 of 1