Graduation Year
2019
Date of Submission
12-2018
Document Type
Campus Only Senior Thesis
Degree Name
Bachelor of Arts
Reader 1
Tzu-Yi Chen
Terms of Use & License Information
Rights Information
© 2018 Varun R Dhananjaya
OCLC Record Number
1089151484
Abstract
In July 2012, a paper by Gutfraind et al. introduced the neighbor-aided network installation problem, which asks for "a minimal cost ordering of the vertices of a graph, where the cost of visiting a node is a function of the number of neighbors that have already been visited." Additionally, in a 2018 paper by Cummings et al., two greedy heuristics were implemented to estimate solutions to the NANIP-Blackstart problem. This paper will evaluate the performance of the greedy heuristics introduced by Cummings et al., and compare their performance to a new heuristic. In addition to comparing heuristics, we will also look at varying the blackstart node and cost function. This analysis will be conducted by testing the heuristics on power networks from the SuiteSparse Matrix Collection and NIST Matrix Market. The goal of this body of work is to better understand the variables at play in the NANIP-Blackstart problem in order to work towards better estimated solutions.
Recommended Citation
Dhananjaya, Varun, "Approximating Solutions for NANIP-Blackstart" (2019). CMC Senior Theses. 2017.
https://scholarship.claremont.edu/cmc_theses/2017
This thesis is restricted to the Claremont Colleges current faculty, students, and staff.