TY - JOUR
T1 - Minimizing the effective graph resistance by adding links is NP-hard
AU - Kooij, Robert E.
AU - Achterberg, Massimo A.
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
KW - Effective graph resistance
KW - Graph augmentation
KW - NP-hard
UR - http://www.scopus.com/inward/record.url?scp=85174340521&partnerID=8YFLogxK
U2 - 10.1016/j.orl.2023.10.002
DO - 10.1016/j.orl.2023.10.002
M3 - Article
AN - SCOPUS:85174340521
SN - 0167-6377
VL - 51
SP - 601
EP - 604
JO - Operations Research Letters
JF - Operations Research Letters
IS - 6
ER -