In an undirected, 2-node connected graph $G=(V,E)$ with positive real edge lengths, the distance between any two nodes $r$ and $s$ is the length of a shortest path between $r$ and $s$ in $G$. The removal of a node and its incident edges from $G$ may increase the distance from $r$ to $s$. A {\em most vital node} of a given shortest path from $r$ to $s$ is a node (other than $r$ and $s$) whose removal from $G$ results in the largest increase of the distance from $r$ to $s$. In the past, the problem of finding a most vital node of a given shortest path has been studied because of its implications in network management, where it is important to know in advance which component failure will affect network efficiency the most. In this paper, we show that this problem can be solved in $O(m + n \log n )$ time and $O(m)$ space, where $m$ and $n$ denote the number of edges and the number of nodes in $G$.

Finding the Most Vital Node of a Shortest Path

Proietti G;
2003

Abstract

In an undirected, 2-node connected graph $G=(V,E)$ with positive real edge lengths, the distance between any two nodes $r$ and $s$ is the length of a shortest path between $r$ and $s$ in $G$. The removal of a node and its incident edges from $G$ may increase the distance from $r$ to $s$. A {\em most vital node} of a given shortest path from $r$ to $s$ is a node (other than $r$ and $s$) whose removal from $G$ results in the largest increase of the distance from $r$ to $s$. In the past, the problem of finding a most vital node of a given shortest path has been studied because of its implications in network management, where it is important to know in advance which component failure will affect network efficiency the most. In this paper, we show that this problem can be solved in $O(m + n \log n )$ time and $O(m)$ space, where $m$ and $n$ denote the number of edges and the number of nodes in $G$.
2003
Istituto di Analisi dei Sistemi ed Informatica ''Antonio Ruberti'' - IASI
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14243/165543
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact