Minimizing the effective graph resistance by adding links is NP-hard

Abstract

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.

References in corpus (2)

• Mitigation of Malicious Attacks on Networks
• A Topological Investigation of Phase Transitions of Cascading Failures in Power Grids

Cited by in corpus (1)

• Efficient Algorithms for Minimizing the Kirchhoff Index via Adding Edges