MSc Thesis Defense by Thomas Nicolaj Barnholdt – University of Copenhagen

MSc Thesis Defense by Thomas Nicolaj Barnholdt

Thomas Nicolaj Barnholdt is defending his MSc thesis.

Title

A generic algorithm for finding multi source multi sink max flow in graphs with small separators

Supervisor: Christian Wulff-Nilsen, Assistant professor at DIKU
External examiner: Rasmus Pagh, Professor at ITU

Abstract

A generic O(s(n) c(n)^2 lg(n) + n lg^2(n) + t(n) lg(n)) algorithm for finding multi source multi sink max flow in an n vertex graph G is given. The graph G must be contained in a graph class with algorithms for finding single source single sink max flow in O(s(n)) time and finding weighted separators of size c(n) in O(t(n)) time. These separators must separate the graph in two parts, such that no part has size greater than pw, for a constant p < 1, where w is the total weight on the vertices of the graph.

Furthermore it is shown, that multi source multi sink max flow in graphs of k-bounded treewidth, for a constant k, can be computed in linear time. Previously this was known for single source single sink max flow.