June 3, Wednesday
14:00 – 15:00
Multiflows and path packing
Graduate seminar
Lecturer : Natalya Vanetik
Affiliation : CS, BGU
Location : 201/37
Host : Graduate seminar
The path packing problem for graphs is defined as follows: given
a supply graph G=(N,E), and a demand graph (T,S), what is the
maximal number of edge-disjoint paths with the end-pair in S in G?
The problem is considered under two assumptions: (1) the node degrees in NT
T are even, and (2) the demand graph satisfies condition defined by A. Karzanov in his 1989 paper.
For any demand graph violating the above condition, the problem is known to be NP-hard even
under (1), and only a few cases satisfying (1) and (2) have been solved.
The talk will address the relation between the path packing problem and an auxiliary flow problem
and will contain a short survey of results achieved in my dissertation.
No special background in graph theory! is required.