The vitality of an arc/node of a graph with respect to the maximum flow between two fixed nodes s and t is defined as the reduction of the maximum flow caused by the removal of that arc/node. In this paper, we address the issue of determining the vitality of arcs and/or nodes for the maximum flow problem. We show how to compute the vitality of all arcs in a general undirected graph by solving only 2(n − 1) max flow instances and, in st‐planar graphs (directed or undirected) we show how to compute the vitality of all arcs and all nodes in O(n) worst‐case time. Moreover, after determining the vitality of arcs and/or nodes, and given a planar embedding of the graph, we can determine the vitality of a “contiguous” set of arcs/nodes in time proportional to the size of the set.
Max flow vitality in general and st‐planar graphs / Ausiello, Giorgio; Franciosa, Paolo G.; Lari, Isabella; Ribichini, Andrea. - In: NETWORKS. - ISSN 0028-3045. - 74:1(2019), pp. 70-78. [10.1002/net.21878]
Max flow vitality in general and st‐planar graphs
Ausiello, Giorgio;Franciosa, Paolo G.;Lari, Isabella;Ribichini, Andrea
2019
Abstract
The vitality of an arc/node of a graph with respect to the maximum flow between two fixed nodes s and t is defined as the reduction of the maximum flow caused by the removal of that arc/node. In this paper, we address the issue of determining the vitality of arcs and/or nodes for the maximum flow problem. We show how to compute the vitality of all arcs in a general undirected graph by solving only 2(n − 1) max flow instances and, in st‐planar graphs (directed or undirected) we show how to compute the vitality of all arcs and all nodes in O(n) worst‐case time. Moreover, after determining the vitality of arcs and/or nodes, and given a planar embedding of the graph, we can determine the vitality of a “contiguous” set of arcs/nodes in time proportional to the size of the set.File | Dimensione | Formato | |
---|---|---|---|
Ausiello_Max-flow-vitality_2019.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
393.35 kB
Formato
Adobe PDF
|
393.35 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.