Friday, 16:15 - 16:40 h, Room: H 3013


Christophe Weibel
When the cut condition is enough: Characterization of multiflow problems by forbidden minors

Coauthors: Amit Chakrabarti, Lisa Fleischer


For a supply graph G=(V,E) and a demand graph H=(V,F),
an assignment of capacities to the
edges of G and demands to the edges of H is said to satisfy the
cut condition if for any cut in the graph, the total demand
crossing the cut is no more than the total capacity crossing it.
The pair (G,H) is called cut-sufficient if for any
assignment of capacities and demands that satisfy the cut condition,
the demands defined on H can be routed within the
network with capacities defined on G.
A pair (G, H) is said to contain another pair (G', H') as a minor
if it is possible to obtain (G', H') from (G, H) by contracting
edges of G and deleting edges of G and H. We propose
to characterize cut-sufficient pairs by forbidden minors.
In particular, we prove a previous conjecture giving the minimal set of forbidden minors
for instances with a series-parallel supply graph, and propose a
conjecture extending our results to planar supply graphs.


Talk 3 of the invited session Fri.3.H 3013
"Flows, cuts, and sparsifiers" [...]
Cluster 2
"Combinatorial optimization" [...]


  payday loans direct . What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.