Back to search

University of Minnesota

Evolving Solutions to Graph Theory Problems

Abstract

dc:description.abstract

Randomized search heuristics such as evolutionary algorithms are general-purposetechniques that have been shown to be effective at solving combinatorial optimiza-tion problems. In this thesis, we use both empirical and theoretical techniques toexamine the use of a simple evolutionary algorithm, the (1+1) EA, applied to com-binatorial optimization problems from graph theory. First, we investigate the evo-lutionary algorithm on problemsk-VertexCover,k-FeedbackVertexSet, andk-OddCycleTransversal, and present Fixed-Parameter Tractable performanceguarantees for the (1+1) EA equipped with a tailored jump-and-repair operator. Wethen follow up with empirical results of the (1+1) EA applied to thek-VertexCoverproblem. Next we move on to investigate the (1+1) EA applied to graceful labeling.We present the first rigorous runtime analysis of an evolutionary algorithm findinggraceful labelings of graphs, and prove polynomial time upper bounds for paths, stars,and complete bipartite graphs with a constant sized partition. To supplement thetheoretical results, we also empirically compare the performance of the (1+1) EA tothat of a complete constraint solver.ii

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Branson, Luke

Subjects

dc:subject × 8

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Citation
Branson, Luke. (2023). Evolving Solutions to Graph Theory Problems. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/258562.

Chain of custody

source
Harvested from
University of Minnesota
Base URL
conservancy.umn.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Branson, Luke. Evolving Solutions to Graph Theory Problems. 2023. https://hdl.handle.net/11299/258562