Skip to main content


eCommons@Cornell

eCommons@Cornell >
Faculty of Computing and Information Science >
Computing and Information Science >
Computing and Information Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/13018
Title: Lexicographic Flow
Authors: Kozen, Dexter
Keywords: flow
Issue Date: 25-Jun-2009
Abstract: The lexicographic flow problem is a flow problem in which the edges are assigned priorities, and we wish to find a flow that is lexicographically maximum with respect to the priority assignment. The problem is reducible to a weighted flow problem, but we show that exponentially large weights are necessary in general. We then give an efficient direct algorithm that does not use weights.
URI: http://hdl.handle.net/1813/13018
Appears in Collections:Computing and Information Science Technical Reports

Files in This Item:

File Description SizeFormat
LexFlow.pdf171.26 kBAdobe PDFView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us