Maximum concurrent flow problems and p-modulus

dc.contributor.authorOrangi-Fard, Negar
dc.date.accessioned2020-07-17T20:31:19Z
dc.date.available2020-07-17T20:31:19Z
dc.date.graduationmonthAugust
dc.date.issued2020-08-01
dc.description.abstractMaximum flow problems involve finding a feasible flow of maximum value through a single source-sink flow network. The flow must satisfy the restriction that the amount of flow into any node other than the source and sink node equals the amount of flow out of it. Moreover, the amount of flow across an edge cannot exceed the capacity of that edge. Maximum multicommodity flow problems are a generalization of maximum flow problems that involve finding an optimal flow between multiple source and sink pairs. The maximum concurrent flow problem is a more complex and popular variation of the maximum multicommodity flow problem, where we are given a set of positive demands and the goal is finding an optimal flow between multiple source-sink pairs. The p-modulus problem provides a general framework for quantifying the richness of a family of objects on a graph. Recent advances in the theory have led to several new interpretations of modulus. In the case of a single source and sink, it has been shown that the single source-sink maximum flow problem is dual to the 1-modulus problem. Similarly, it is known that 2-modulus is related to effective resistances and p-modulus is related to the shortest path problem. Inspired by these properties of single source-sink networks, we show that the maximum concurrent flow problem can be embedded into a one-parameter family of p-modulus problems. Using the flexibility provided by the modulus framework, this allows us to introduce a family of generalizations of p-modulus problems. This connection to modulus provides a natural generalization of effective resistance and shortest path to networks with multiple source-sink pairs.
dc.description.advisorNathan Albin
dc.description.degreeDoctor of Philosophy
dc.description.departmentDepartment of Mathematics
dc.description.levelDoctoral
dc.identifier.urihttps://hdl.handle.net/2097/40749
dc.language.isoen
dc.publisherKansas State University
dc.rights© the author. This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subjectModulus
dc.subjectMaximum concurrent flow problem
dc.subjectMaximum multicommodity flow problem
dc.titleMaximum concurrent flow problems and p-modulus
dc.typeDissertation

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
NegarOrangiFard2020.pdf
Size:
657.87 KB
Format:
Adobe Portable Document Format
Description:

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.62 KB
Format:
Item-specific license agreed upon to submission
Description: