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

Journal article (2023)

Authors

Robert Kooij Quantum & Computer Engineering , TNO
M.A. Achterberg Network Architectures and Services - EEMCS
Department
Quantum & Computer Engineering
Copyright: © 2023 Robert Kooij, M.A. Achterberg
DOI: https://doi.org/10.1016/j.orl.2023.10.002
More Info
expand_more

Published Date

2023

Language

English

Department

Quantum & Computer Engineering

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.