dc.contributor.advisor Burtscher, Martin dc.contributor.author van Til, Isaac Willem ( ) dc.date.accessioned 2020-07-20T19:18:51Z dc.date.available 2020-07-20T19:18:51Z dc.date.issued 2020-05 dc.identifier.citation van Til, I. W. (2020). Efficient vertex-centric graph coloring (Unpublished thesis). Texas State University, San Marcos, Texas. en_US dc.identifier.uri https://digital.library.txstate.edu/handle/10877/12129 dc.description.abstract Graph coloring is a way of labeling (with labels traditionally referred to as “colors”) the elements of a graph with the constraint that no two adjacent vertices have the same color and that as few colors should be used as possible. In addition to many theoretical problems, graph coloring lends itself to efficiently solving a variety of practical applications (e.g., schedule generation, resource allocation, networking, and solving Sudoku). The problem with graph coloring is that finding a solution with the minimal number of colors is NP-hard, i.e., no known polynomial time algorithm can solve it optimally (so computing the solution cannot be done quickly). I have written a series of algorithms that take advantage of high amounts of parallelization to produce acceptable colorings. An analysis of the colorings and runtimes of each approach compared to other solutions from the literature shows that acceptable colorings are produced in a reasonable time. en_US dc.format Text dc.format.extent 19 pages dc.format.medium 1 file (.pdf) dc.language.iso en dc.subject Graph coloring heuristic en_US dc.subject Parallel algorithm en_US dc.subject OpenMP en_US dc.subject Many-core architecture en_US dc.subject Vertex coloring en_US dc.title Efficient Vertex-Centric Graph Coloring en_US txstate.documenttype Thesis thesis.degree.department Honors College thesis.degree.discipline Computer Science thesis.degree.grantor Texas State University dc.description.department Honors College
﻿