Show simple item record

dc.contributor.advisorBurtscher, Martin
dc.contributor.authorvan Til, Isaac Willem ( )
dc.date.accessioned2020-07-20T19:18:51Z
dc.date.available2020-07-20T19:18:51Z
dc.date.issued2020-05
dc.identifier.citationvan Til, I. W. (2020). Efficient vertex-centric graph coloring (Unpublished thesis). Texas State University, San Marcos, Texas.en_US
dc.identifier.urihttps://digital.library.txstate.edu/handle/10877/12129
dc.descriptionPresented to the Honors Committee of Texas State University in Partial Fulfillment of the Requirements for Graduation in the University Honors Program, May 2020.en_US
dc.description.abstractGraph 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.formatText
dc.format.extent19 pages
dc.format.medium1 file (.pdf)
dc.language.isoen_USen_US
dc.subjectGraph coloring heuristicen_US
dc.subjectParallel algorithmen_US
dc.subjectOpenMPen_US
dc.subjectMany-core architectureen_US
dc.subjectVertex coloringen_US
dc.titleEfficient Vertex-Centric Graph Coloringen_US
txstate.documenttypeThesis
thesis.degree.departmentHonors College
thesis.degree.disciplineComputer Science
thesis.degree.grantorTexas State University
txstate.departmentHonors College


Download

Thumbnail

This item appears in the following Collection(s)

Show simple item record