Flow in Planar Graphs with Vertex Capacities
| dc.contributor.author | Khuller, Samir | en_US |
| dc.contributor.author | Naor, Joseph | en_US |
| dc.date.accessioned | 2007-04-23T17:44:47Z | |
| dc.date.available | 2007-04-23T17:44:47Z | |
| dc.date.issued | 1990-01 | en_US |
| dc.description.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). | en_US |
| dc.format.extent | 2112781 bytes | |
| dc.format.extent | 588204 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1089 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/6929 | |
| dc.language.iso | en_US | en_US |
| dc.publisher | Cornell University | en_US |
| dc.subject | computer science | en_US |
| dc.subject | technical report | en_US |
| dc.title | Flow in Planar Graphs with Vertex Capacities | en_US |
| dc.type | technical report | en_US |