Re: Flow Decomposition

RamT wrote:
Hello everyone,

Imagine a capacitated graph with a supply and multiple demands.
Provided there already exists a of flow that emanates from the source
and terminates at all sinks (the flow does not violate any link
capacity and the flow is consistent). If I were to decompose the flow
into simple paths for each sink in sequence. Is there possibility that
I may encounter a problem where decomposing for one sink (and deducting
the appropriate flow amount from the graph) will hinder decomposition
for the next sink (because the source and the (next) sink become
disjoint with respect to the remaining flow in the graph)?

I hope there isn't such problem. Up to now I have yet to construct an
example which can cause the problem I mentioned. Is there anyone out
there who can construct a simple example which can exhibit the problem?

Thank you.


Yes, I think there could be.

Consider the following case:

1 source, 2 sinks, 5 other nodes (A,B,C,D,E)
edges:
e(source,A,2),
e(source,B,2),
e(source,C,1),
e(A,D,2),
e(B,D,2),
e(B,E,1),
e(C,E,2),
e(D,sink_1,2),
e(E,sink_2,2)

The maximal flow would be (source,A,2),(A,D,2),(D,sink_1,2),(source,B,1),(source,C,1),(B,E,1),(C,E,1),(E,sink_2,2)
with a total flow of 4.

If you would first decompose sink_1, and take the flow as (source,B,2),(B,D,2),(D,sink_1,2) and then decompose for sink_2, you would get a total flow of 3.

--
robby goetschalckx
.

Relevant Pages

  • Re: Discussion regarding Mr. Diabys algorithm
    ... graph - one level of graph was representation of one parenthesis, ... remembered "flow" through every arc. ... from "cut point" to end) but could we possibly store tape contents with less ...
    (comp.theory)
  • Flow Decomposition
    ... Imagine a capacitated graph with a supply and multiple demands. ... Provided there already exists a of flow that emanates from the source ... I may encounter a problem where decomposing for one sink (and deducting ...
    (comp.theory)
  • Re: Combinatorics Designated Driver Problem
    ... We want to find some way to assign a driver to ... Consider the bipartite directed graph with source vertices corresponding ... S_i units of flow, and sink d demands 1 unit. ... person i drives on day d if the flow from i to d is 1. ...
    (sci.math)
  • Re: Extended counter-example for extended M.Diaby Linear Model
    ... "node" in the graph in my papers. ... representation that respects all the constraints of my model will have ... that flow starts from node 1. ... or reduction is incorrect :-). ...
    (comp.theory)
  • Re: Extended counter-example for extended M.Diaby Linear Model
    ... Cost] while model return solution without even one. ... algorithm how to get this flow. ... Original graph has at least 2 mln (that is how many I have found to ... Indicate what arcs are "external arcs" (may be, ...
    (comp.theory)