{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/68182"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/68182","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Maximum Flows in Unit-Capacitated Multicommodity Trees","abstract":"Multicommodity flows are studied, in the special case where the underlying graph is a tree and all arc capacities are one.","abstract_html":"Multicommodity flows are studied, in the special case where the underlying graph is a tree and all arc capacities are one.","abstract_has_math":false,"creators":["Lobb, Wayne Anthony"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-14T13:09:50Z","date_published":"2014-12-14T13:09:50Z","updated_at":"2026-07-22T22:25:58Z","subjects":["Mathematics"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI8114446"],"render_values":[{"text":"(UMI)AAI8114446","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/68182","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Lobb, Wayne Anthony"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-14T13:09:50Z","1981"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/68182","(UMI)AAI8114446"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2014-12-14T13:09:50Z (GMT). No. of bitstreams: 1 8114446.pdf: 2272157 bytes, checksum: 931b141b53bf2611fedf0ff4630648ea (MD5) Previous issue date: 1981","Embargo set by: Seth Robbins for item 68360 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Open Restriction set for Item 68360 on 2022-01-06T18:24:45Z with date null by eliasbh2@illinois.edu.","Open Restriction set for Item 68360 on 2022-01-06T18:24:48Z with date null by eliasbh2@illinois.edu.","Open","94 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1981."]},{"key":"dc:title","label":"Title","values":["Maximum Flows in Unit-Capacitated Multicommodity Trees"]}]}],"canonical_facts":{"dc:creator":["Lobb, Wayne Anthony"],"dc:date":["2014-12-14T13:09:50Z","1981"],"dc:description":["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.","Made available in DSpace on 2014-12-14T13:09:50Z (GMT). No. of bitstreams: 1 8114446.pdf: 2272157 bytes, checksum: 931b141b53bf2611fedf0ff4630648ea (MD5) Previous issue date: 1981","Embargo set by: Seth Robbins for item 68360 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Open Restriction set for Item 68360 on 2022-01-06T18:24:45Z with date null by eliasbh2@illinois.edu.","Open Restriction set for Item 68360 on 2022-01-06T18:24:48Z with date null by eliasbh2@illinois.edu.","Open","94 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1981."],"dc:identifier":["http://hdl.handle.net/2142/68182","(UMI)AAI8114446"],"dc:language":["eng"],"dc:subject":["Mathematics"],"dc:title":["Maximum Flows in Unit-Capacitated Multicommodity Trees"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:58Z"}