We study the problem of computing the vitality of edges and vertices with respect to the st-max flow in undirected planar graphs, where the vitality of an edge/vertex is the st-max flow decrease when the edge/vertex is removed from the graph. This allows us to establish the vulnerability of the graph with respect to the st-max flow. We give efficient algorithms to compute an additive guaranteed approximation of the vitality of edges and vertices in planar undirected graphs. We show that in the general case high vitality values are well approximated in time close to the time currently required to compute st-max flow O(n log log n). We also give improved, and sometimes optimal, results in the case of integer capacities. All our algorithms work in O(n) space.
How vulnerable is an undirected planar graph with respect to max flow / Balzotti, Lorenzo; Franciosa, Paolo G.. - In: NETWORKS. - ISSN 0028-3045. - (2024), pp. 1-17. [10.1002/net.22205]
How vulnerable is an undirected planar graph with respect to max flow
Balzotti, Lorenzo
Membro del Collaboration Group
;Franciosa, Paolo G.Membro del Collaboration Group
2024
Abstract
We study the problem of computing the vitality of edges and vertices with respect to the st-max flow in undirected planar graphs, where the vitality of an edge/vertex is the st-max flow decrease when the edge/vertex is removed from the graph. This allows us to establish the vulnerability of the graph with respect to the st-max flow. We give efficient algorithms to compute an additive guaranteed approximation of the vitality of edges and vertices in planar undirected graphs. We show that in the general case high vitality values are well approximated in time close to the time currently required to compute st-max flow O(n log log n). We also give improved, and sometimes optimal, results in the case of integer capacities. All our algorithms work in O(n) space.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.