Determining Connectivity in a Failed Network

The disclosed technology, in one embodiment, involves a method that improves the execution speed of graph algorithms that are commonly used by network service providers for network analysis and/or design. The disclosed technology can be used to provide significant efficiency improvements when applied to networks that are separated into several isolated fragments (“fragmented networks”) due to severe damage that may be caused by either natural disaster (such as hurricanes or earthquakes), or planned adversary attacks. In one embodiment of the disclosed technology, a graph algorithm, that is used to determine a characteristic of the network, is not applied directly to the whole network/graph. Instead, the graph algorithm is applied to isolated network/graph fragments that are identified, for example, by using a fragment discovery algorithm. The graph algorithm is then applied to one or more relevant fragments. The results may be combined to obtain a network wide result.