\"The graph coloring problem, which is to color the vertices of a simple undirected graph with the minimum number of colors such that no adjacent vertices are assigned the same color, arises in a variety of scheduling problems. This dissertation focuses attention on vertex sequential coloring. Two basic approaches, backtracking and branch-and-bound, serve as a foundation for the developed algorithms. The various algorithms have been programmed and applied to random graphs. This dissertation will present several variations of the Korman algorithm, Korw2, Pactual, and Pactmaxw2, which produce exact colorings quicker than the Korman algorithm in the average for some classes of graphs. In addition to exact algorithms, we also look at some heuristic algorithms, limit, epsilon, and branch-and-bound.\"--Abstract, page ii.
","abstract_html":"<p>"The graph coloring problem, which is to color the vertices of a simple undirected graph with the minimum number of colors such that no adjacent vertices are assigned the same color, arises in a variety of scheduling problems. This dissertation focuses attention on vertex sequential coloring. Two basic approaches, backtracking and branch-and-bound, serve as a foundation for the developed algorithms. The various algorithms have been programmed and applied to random graphs. This dissertation will present several variations of the Korman algorithm, Korw2, Pactual, and Pactmaxw2, which produce exact colorings quicker than the Korman algorithm in the average for some classes of graphs. In addition to exact algorithms, we also look at some heuristic algorithms, limit, epsilon, and branch-and-bound."--Abstract, page ii.</p>","abstract_has_math":false,"creators":["Lin, Shi-Jen"],"institution":"University of Missouri--Rolla","degree_name":"Ph. D. in Computer Science","degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016-02-10T08:00:00Z","date_published":"2016-02-10T08:00:00Z","updated_at":"2026-07-24T03:19:21Z","subjects":["Computer Sciences"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://scholarsmine.mst.edu/doctoral_dissertations/736","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Lin, Shi-Jen"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2016-02-10T08:00:00Z"]},{"key":"dc:type","label":"Dc Type","values":["Dissertation - Open Access"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph. D. in Computer Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Missouri--Rolla"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Sciences"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://scholarsmine.mst.edu/doctoral_dissertations/736"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["\"The graph coloring problem, which is to color the vertices of a simple undirected graph with the minimum number of colors such that no adjacent vertices are assigned the same color, arises in a variety of scheduling problems. This dissertation focuses attention on vertex sequential coloring. Two basic approaches, backtracking and branch-and-bound, serve as a foundation for the developed algorithms. The various algorithms have been programmed and applied to random graphs. This dissertation will present several variations of the Korman algorithm, Korw2, Pactual, and Pactmaxw2, which produce exact colorings quicker than the Korman algorithm in the average for some classes of graphs. In addition to exact algorithms, we also look at some heuristic algorithms, limit, epsilon, and branch-and-bound.\"--Abstract, page ii.
"]},{"key":"dc:title","label":"Title","values":["Graph coloring algorithms on random graphs"]}]}],"canonical_facts":{"dc:creator":["Lin, Shi-Jen"],"dc:date.available":["2016-02-10T08:00:00Z"],"dc:description.abstract":["\"The graph coloring problem, which is to color the vertices of a simple undirected graph with the minimum number of colors such that no adjacent vertices are assigned the same color, arises in a variety of scheduling problems. This dissertation focuses attention on vertex sequential coloring. Two basic approaches, backtracking and branch-and-bound, serve as a foundation for the developed algorithms. The various algorithms have been programmed and applied to random graphs. This dissertation will present several variations of the Korman algorithm, Korw2, Pactual, and Pactmaxw2, which produce exact colorings quicker than the Korman algorithm in the average for some classes of graphs. In addition to exact algorithms, we also look at some heuristic algorithms, limit, epsilon, and branch-and-bound.\"--Abstract, page ii.
"],"dc:identifier":["https://scholarsmine.mst.edu/doctoral_dissertations/736"],"dc:subject":["Computer Sciences"],"dc:title":["Graph coloring algorithms on random graphs"],"dc:type":["Dissertation - Open Access"],"thesis:degree_name":["Ph. D. in Computer Science"],"thesis:institution_name":["University of Missouri--Rolla"]},"updated_at":"2026-07-24T03:19:21Z"}