Flow in planar graphs with vertex capacities | Zendy

Samir Khuller | Zendy; Joseph Naor | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Flow in planar graphs with vertex capacities

Author(s) -

Samir Khuller,

Joseph Naor

Publication year - 1994

Publication title -

algorithmica

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.647

H-Index - 78

eISSN - 1432-0541

pISSN - 0178-4617

DOI - 10.1007/bf01240733

Subject(s) - planar , planar graph , vertex (graph theory) , mathematics , combinatorics , planar straight line graph , context (archaeology) , theory of computation , enhanced data rates for gsm evolution , flow (mathematics) , reduction (mathematics) , 1 planar graph , discrete mathematics , graph , chordal graph , computer science , algorithm , geometry , telecommunications , paleontology , computer graphics (images) , biology

Max-flow in planar graphs has always been studied with the assumption that there are capacities only on the edges. Here we consider a more general version of the problem when the vertices as well as edges have capacity constraints. In the context of general graphs considering only edge capacities is not restrictive, since the vertex-capacity problem can be reduced to the edge-capacity problem. However, in the case of planar graphs this reduction does not maintainplanarity and cannot be used. We study different versions of the planar flow problem (all of which have been extensively investigated in the context of edge capacities).

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research