Campus Event Calendar
Event Entry
What and Who
Single source unsplittable flows
Yefim Dinitz
Technion, Israel
AG1 Mittagsseminar
AG 1, AG 2
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 17 December 97
13:30
60 Minutes
MPI
024
Saarbrücken
Abstract
Consider a network with one source and multiple sinks.
Each sink has a demand (at most 1) associated with it.
The unsplittable flow problem is to route these demands from source
to sinks unsplittably (i.e. each demand should be routed along one
path). We show that if there is a fractional flow satisfying demands,
then there is an unsplittable flow which violates the capacity of
any edge by at most the maximum demand.
Contact
Yefim Dinitz
508
--email hidden
passcode not visible
logged in users only