Files in this item



application/pdf8114446.pdf (2MB)Restricted to U of Illinois
(no description provided)PDF


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.
Issue Date:1981
Description:94 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1981.
Other Identifier(s):(UMI)AAI8114446
Date Available in IDEALS:2014-12-14
Date Deposited:1981

This item appears in the following Collection(s)

Item Statistics