An Exploration of the Network Installation and Recovery Problem with Blackstart Nodes

摘要

The Neighbor Aided Network Installation Problem asks how best to install the nodes in a network under the assumption that the cost of installing a node depends solely on the number of its neighbors which have been previously installed. We study a version which incorporates blackstart nodes into the model. Under the assumption of a decreasing convex cost function and a single blackstart node, we solve the problem for subclasses of almost-complete and augmented-tree networks. We also describe two heuristics and present experimental results on real world networks.