Out-of-Core Graph Coloring Algorithm

Simple item page
dc.contributor.advisorBurtscher, Martin
dc.contributor.authorLiu, Yiqian
dc.contributor.committeeMemberGu, Qijun
dc.contributor.committeeMemberIslam, Tanzima
dc.date.accessioned2020-07-30T21:37:55Z
dc.date.available2020-07-30T21:37:55Z
dc.date.issued2020-08
dc.description.abstractOut-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.departmentComputer Science
dc.formatText
dc.format.extent55 pages
dc.format.medium1 file (.pdf)
dc.identifier.citationLiu, Y. (2020). <i>Out-of-core graph coloring algorithm</i> (Unpublished thesis). Texas State University, San Marcos, Texas.
dc.identifier.urihttps://hdl.handle.net/10877/12256
dc.language.isoen
dc.subjectOut-of-core algorithm
dc.subjectGraph coloring
dc.subject.lcshComputer algorithms
dc.subject.lcshGraph coloring
dc.titleOut-of-Core Graph Coloring Algorithm
dc.typeThesis
thesis.degree.departmentComputer Science
thesis.degree.disciplineComputer Science
thesis.degree.grantorTexas State University
thesis.degree.levelMasters
thesis.degree.nameMaster of Science

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
LIU-THESIS-2020.pdf
Size:
1.01 MB
Format:
Adobe Portable Document Format
Download

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
4.52 KB
Format:
Plain Text
Description:
Download
No Thumbnail Available
Name:
LICENSE.txt
Size:
2.96 KB
Format:
Plain Text
Description:
Download

Collections

Graduate Theses and Dissertations