Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computing and Information Science
  4. Computing and Information Science Technical Reports
  5. Hierarchical Flow

Hierarchical Flow

File(s)
TR2004-1965.pdf (2.27 MB)
Permanent Link(s)
https://hdl.handle.net/1813/5665
Collections
Computing and Information Science Technical Reports
Author
Hartline, Jeff
Sharp, Alexa
Abstract

This paper defines a hierarchical version of the maximum flow problem. In this model, the capacities increase over time and the resulting solution is a sequence of flows that build on each other incrementally. Thus far, hierarchical problems considered in the literature have been built on NP-complete problems. To the best of our knowledge, our results are the first to find a polynomial time problem whose hierarchical version is NP-complete. We present approximation algorithms and hardness results for many versions of this problem, and comment on the relation to multicommodity flow.

Date Issued
2004-09-29
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2004-1965
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

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