Premium
Max flow vitality in general and st ‐planar graphs
Author(s) -
Ausiello Giorgio,
Franciosa Paolo G.,
Lari Isabella,
Ribichini Andrea
Publication year - 2019
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21878
Subject(s) - vitality , embedding , maximum flow problem , mathematics , planar graph , graph , combinatorics , arc (geometry) , planar , flow (mathematics) , undirected graph , book embedding , node (physics) , set (abstract data type) , flow network , discrete mathematics , computer science , pathwidth , geometry , line graph , artificial intelligence , physics , philosophy , theology , computer graphics (images) , quantum mechanics , programming language
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.