Graduation Year


Date of Submission


Document Type

Campus Only Senior Thesis

Degree Name

Bachelor of Arts

Reader 1

Tzu-Yi Chen

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Rights Information

© 2018 Varun R Dhananjaya

OCLC Record Number



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.

This thesis is restricted to the Claremont Colleges current faculty, students, and staff.