Minimizing the effective graph resistance by adding links is NP-hard
article
The effective graph resistance, also known as the Kirchhoff index, is metric that is used to quantify the robustness of a network. We show that the optimisation problem of minimizing the effective graph resistance of a graph by adding a fixed number of links, is NP-hard.
TNO Identifier
1003385
Source
Operations Research Letters, 51, pp. 1-4.
Pages
1-4