Maximum Flows in Unit-Capacitated Multicommodity Trees

Lobb, Wayne Anthony

Permalink

https://hdl.handle.net/2142/68182 Copy

Description

Title

Maximum Flows in Unit-Capacitated Multicommodity Trees

Author(s)

Lobb, Wayne Anthony

Issue Date

1981

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

Mathematics

Language

eng

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.

Graduation Semester

1981

Type of Resource

text

Permalink

http://hdl.handle.net/2142/68182

Owning Collections