1
$\begingroup$

In the network clearance problem, we are given a simple undirected graph with a capacity assigned to each edge (and/or to each vertex). Each edge can transport up to its capacity each time step (i.e., if the edge has capacity 2, it can transport 2 units of flow in each time step). Each vertex is either a source vertex ($\in S$) or a destination vertex ($\in T$). Initially, there is a constant, possibly zero, amount of a substance in each of the nodes in $S$. The capacity of $T$ vertices is infinite. The question is how long does it take to transfer the substance from all the $S$ vertices to some $T$ vertices.

This can be seen as a network of tanks connected with pipes. Each tank in set $S$ contains some water. We want to empty the water from tanks $S$ to tanks $T$ considering the limited capacity of the pipes.

The network clearance problem seems similar to the network flow problem. The main difference is that in the former problem, there is a limited amount of the substance, not a continuous demand and we want to minimize the time rather than maximizing the flow. However, it seems to me that a variation of the residual graph can be used to solve this problem.

I came up with a solution that seems promising. But, I am still interested in related work or better algorithms. So, if you know other related work to this problem or a more efficient algorithm, please inform me.

My algorithm actually works on the decision version of the network clearance problem. Given a time bound $b$, the question is that if it is possible to clear the network in $b$ units of time or not.

The algorithm that I came up with is as follows. For a given network $G$, create a new graph $G'$ with all the nodes and edges of $G$. Set the capacity of each edge $e$ of $G'$ to $b$ times the capacity of the corresponding edge in $G$. Add two vertices $s$ and $t$ to $G'$. For each vertex $v \in S$ add an edge $\langle s,v \rangle$ to $G'$ with capacity equal to demand of $v$ in $G$. For each $u \in T$ add an edge $\langle u, t \rangle$ to $G'$ with capacity infinity.

The answer to the decision question is yes if and only if the maximum flow between $s$ and $t$ in $G'$ is equal to summation of demands in $G$.

One can simply use one of the known algorithms for Maximum Flow to solve the decision problem. Having the solution to the decision version, we can binary search over the bound to find the smallest bound for which the answer to the question is yes.

Do you know of a better algorithm, or a reference in the literature where this problem has been considered before?

$\endgroup$
  • 1
    $\begingroup$ "how long" -- how does time work here? Each edge can transport its weight each time step? $\endgroup$ – Raphael Feb 25 '15 at 8:16
  • $\begingroup$ @Raphael: right. $\endgroup$ – Helium Feb 25 '15 at 8:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.