Huraian
During the last years Fiber-optic based communication networks have become affordable for individual households. Due to the costly nature of the materials and infrastructure that have to be deployed to distribute such a network over a large area, exact algorithms for cal- culating a provably optimal cable routing are desirable. However, due to the computational complexity of the problem, such algorithms are not always able to determine an optimal solution within acceptable time.