Dissertation/Thesis Abstract

A Score Minimizing Vertex Partitioning Algorithm Using Simulated Annealing
by Simone, Nicholas S., M.A., Saint Louis University, 2019, 75; 27671208
Abstract (Summary)

Let G be a graph and c(i) be a scoring function that assigns a nonnegative real number to each partition of vertices into n disjoint sets. We create an algorithm for finding a partition that minimizes the scoring function and show how this can be used to find, or approximate, solutions to well-known hard problems in graph theory.

This paper includes the r-package savi, which implements simulated annealing. Specifically, we implement it for three example vertex partitioning problems: vertex covering, identifying k-partite graphs, and the Erdős–Faber–Lovász Conjecture. The paper also shows which scoring functions to use for these examples and provides proofs that the scoring functions assign their lowest value to the optimal score.

Indexing (document details)
Advisor: Speegle, Darrin
Commitee: Johnson, Brody, Chambers, Erin Wolf
School: Saint Louis University
Department: Mathematics
School Location: United States -- Missouri
Source: MAI 81/7(E), Masters Abstracts International
Subjects: Mathematics
Keywords: Optimization, Simulated annealing, Vertex partitioning
Publication Number: 27671208
ISBN: 9781392577172
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy