Flow in planar graphs with vertex capacities

Samir Khuller*, Joseph (Seffi) Naor

*Corresponding author for this work

Research output: Contribution to journalArticle

22 Scopus citations

Abstract

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 maintain planarity 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).

Original languageEnglish (US)
Pages (from-to)200-225
Number of pages26
JournalAlgorithmica
Volume11
Issue number3
DOIs
StatePublished - Mar 1 1994

Keywords

  • Circulation problem
  • Network flow
  • Planar graphs
  • Vertex capacities

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Flow in planar graphs with vertex capacities'. Together they form a unique fingerprint.

  • Cite this