Files in this item
|(no description provided)|
|Title:||Maximum Flows in Unit-Capacitated Multicommodity Trees|
|Author(s):||Lobb, Wayne Anthony|
|Department / Program:||Mathematics|
|Degree Granting Institution:||University of Illinois at Urbana-Champaign|
|Abstract:||Multicommodity flows are studied, in the special case where the underlying graph is a tree and all arc capacities are one.
If no commodity path contains more than two arcs, or if no arc is contained in more than two commodity paths, then the solution modularity--the denominator of the maximum total flow--is no greater than two. Examples show that these conditions cannot be weakened, and that modularity can grow exponentially in the number of commodities even under very restrictive conditions.
Results of Berge and Lovasz about hypergraphs are applied, to show that maximum flow in integers equals minimum cut, in the absence of generalized odd cycles. This fact is used to show that the intersection graphs of certain multicommodity trees form a new class of graphs for which Berge's Strong Perfect Graph Conjecture holds.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1981.
|Date Available in IDEALS:||2014-12-14|