Dear All,
Our client wants to compete for the construction of a complete sewage system, which includes the construction of sewage pipes in more than 200 streets.
During the construction streets will be closed, and some of them will be closed at the same time. It is a requirement (and we should prove it now in the tender phase) that despite of the cut offs (blockades) of the streets all the adresses will be accessible from everywhere.
At the same time - as deadline is tight - we want to start the construction at as many as possible streets.
What we have is the topology (graph) of the city. From matemathical point of view it is quite clear (we have to look for the minimal spanning tree, and we can close all the other roads) If you have any other suggestion that can solve this problem please let me know.
If you have any application even in Excel that can handle this problem please let me know. (I do not want to waste my time on developing an application for this)
I also would like to know if anyone of you had encountered this kind of problem before
Thanks in advance
Miklós