Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Flow in Planar Graphs with Vertex Capacities

Flow in Planar Graphs with Vertex Capacities

File(s)
90-1089.pdf (2.01 MB)
90-1089.ps (574.42 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6929
Collections
Computer Science Technical Reports
Author
Khuller, Samir
Naor, Joseph
Abstract

Max-flow in planar graphs has always been studies 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 in not restrictive, since one can reduce the vertex capacity problem 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).

Date Issued
1990-01
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1089
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance