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" [...]


  Today, Ohio Loans Online are legitimate, but there are illegal transactions that are still on the rise. If you have already decided to take Levitra For Sale, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.