We study the problem of computing the vitality of edges and vertices with respect to \$st\$-max flow in undirected planar graphs, where the vitality of an edge/vertex in a graph with respect to max flow between two fixed vertices \$s,t\$ is defined as the max flow decrease when the edge/vertex is removed from the graph. We show that a \$delta\$ additive approximation of the vitality of all edges with capacity at most \$c\$ can be computed in \$O(rac{c}{delta}n +n log log n)\$ time, where \$n\$ is the size of the graph. A similar result is given for the vitality of vertices. All our algorithms work in \$O(n)\$ space.

Max Flow Vitality of Edges and Vertices in Undirected Planar Graphs / Balzotti, Lorenzo; Franciosa, Paolo G.. - (2022).

### Max Flow Vitality of Edges and Vertices in Undirected Planar Graphs

#### Abstract

We study the problem of computing the vitality of edges and vertices with respect to \$st\$-max flow in undirected planar graphs, where the vitality of an edge/vertex in a graph with respect to max flow between two fixed vertices \$s,t\$ is defined as the max flow decrease when the edge/vertex is removed from the graph. We show that a \$delta\$ additive approximation of the vitality of all edges with capacity at most \$c\$ can be computed in \$O(rac{c}{delta}n +n log log n)\$ time, where \$n\$ is the size of the graph. A similar result is given for the vitality of vertices. All our algorithms work in \$O(n)\$ space.
##### Scheda breve Scheda completa
2022
2331-8422
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11573/1638680`
##### Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

##### Citazioni
• ND
• ND
• ND