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

Robert E. Kooij*, Massimo A. Achterberg

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

5 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)601-604
Number of pages4
JournalOperations Research Letters
Volume51
Issue number6
DOIs
Publication statusPublished - 2023

Keywords

  • Effective graph resistance
  • Graph augmentation
  • NP-hard

Fingerprint

Dive into the research topics of 'Minimizing the effective graph resistance by adding links is NP-hard'. Together they form a unique fingerprint.

Cite this