More homology flows

Flows and cuts have been the topic of much study since Ford and Fulkerson's original paper. The problem we look at is the computation of flows on some generalizations of planar graphs. In particular, the input graph can be embedded on a surface of genus g, and has the source and sink on the same face. We show this problem can be reduced to a convex programming problem in dimension 2g, and also show some interesting properties of the feasible polytope.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2010

Author dc:creator

• Sundar, Aparna

Contributors dc:contributor

• Erickson, Jeff G.

• Homology Flows
• ellipsoid method

Statement dc:rights

• Copyright 2010 Aparna Sundar

Language dc:language

en

Handle dc:identifier

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

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/16487