Max flow vitality in general and st-planar graphs

DOI10.1002/NET.21878zbMATH Open1418.90268arXiv1710.01965OpenAlexW2962797154MaRDI QIDQ5226589FDOQ5226589

Authors: Andrea Ribichini, Giorgio Ausiello, Paolo G. Franciosa, Isabella Lari 

Publication date: 1 August 2019

Published in: Networks (Search for Journal in Brave)

Abstract: The emph{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.

Full work available at URL: https://arxiv.org/abs/1710.01965

Recommendations

• Finding the \(k\) most vital elements of an s-t planar directed network
• Maximizing residual flow under an arc destruction
• Maximum flow in directed planar graphs with vertex capacities
• Maximum Flow in Directed Planar Graphs with Vertex Capacities
• An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks

zbMATH Keywords

vitalitymaximum flowminimum cutplanar graphsgeneral graphsfault resiliency

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cited In (9)

• Finding the \(k\) most vital elements of an s-t planar directed network
• Non-crossing shortest paths lengths in planar graphs in linear time
• The all-pairs vitality-maximization (VIMAX) problem
• How vulnerable is an undirected planar graph with respect to max flow
• Maximizing residual flow under an arc destruction
• How vulnerable is an undirected planar graph with respect to max flow
• A dichotomy result for cyclic-order traversing games
• Non-crossing shortest paths lengths in planar graphs in linear time
• Non-crossing shortest paths in undirected unweighted planar graphs in linear time

This page was built for publication: Max flow vitality in general and \(st\)-planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5226589)