Max flow vitality in general and  st ‐planar graphs | Zendy

Ausiello Giorgio | Zendy; Franciosa Paolo G. | Zendy; Lari Isabella | Zendy; Ribichini Andrea | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research