The Gilbert arborescence problem
MG Volz, M Brazil, CJ Ras, KJ Swanepoel, DA Thomas
Networks | WILEY | Published : 2013
We investigate the problem of designing a minimum-cost flow network interconnecting n sources and a single sink, each with known locations in a normed space and with associated flow demands. The network may contain any finite number of additional unprescribed nodes from the space; these are known as the Steiner points. For concave increasing cost functions, a minimum-cost network of this sort has a tree topology, and hence can be called a Minimum Gilbert Arborescence (MGA). We characterize the local topological structure of Steiner points in MGAs, showing, in particular, that for a wide range of metrics, and for some typical real-world cost functions, the degree of each Steiner point is 3. ©..View full abstract
Contract grant sponsor: Newmont Australia Limited and University of Melbourne [ARC Linkage Grant]Part of this research was done while Marcus Volz was a PhD student at The University of Melbourne. Much of this article was written while Konrad Swanepoel was visiting the Department of Mechanical Engineering of The University of Melbourne on a Tewkesbury Fellowship.