Flow Decomposition
- From: "RamT" <rambotrout@xxxxxxxxx>
- Date: 7 Dec 2006 06:54:21 -0800
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.
.
- Follow-Ups:
- Re: Flow Decomposition
- From: Robby Goetschalckx
- Re: Flow Decomposition
- Prev by Date: Re: A stupid thought about Hamilton Path problem
- Next by Date: Re: An easy way to prove P != NP
- Previous by thread: Re: Minimizing length of a document
- Next by thread: Re: Flow Decomposition
- Index(es):
Relevant Pages
|
