The Gilbert arborescence problem

DOI10.1002/NET.21475zbMATH Open1269.90026arXiv0909.4270OpenAlexW3101920128WikidataQ61714613 ScholiaQ61714613MaRDI QIDQ5326792FDOQ5326792

Authors: M. G. Volz, Konrad J. Swanepoel, M. Brazil, C. J. Ras, D. A. Thomas 

Publication date: 6 August 2013

Published in: Networks (Search for Journal in Brave)

Abstract: 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 characterise 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.

Full work available at URL: https://arxiv.org/abs/0909.4270

Recommendations

• The arborescence-realization problem
• Turán's problem for trees
• Trees and Keisler's problem
• A solution to an Ambarzumyan problem on trees
• On a problem of linear arboricity
• scientific article; zbMATH DE number 7692724
• The arithmetic of trees
• scientific article; zbMATH DE number 1638647
• scientific article; zbMATH DE number 1890833
• Arborescence optimization problems solvable by Edmonds' algorithm

zbMATH Keywords

network flowsSteiner treeminimum-cost networkGilbert network

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Network design and communication in computer systems (68M10)

Cites Work

• The Steiner tree problem
• Paired calibrations applied to soap films, immiscible fluids, and surfaces or networks minimizing other norms
• Minimum cost flow‐dependent communication networks
• Optimal Design of Gas Pipeline Networks
• Low cost drainage networks
• The local Steiner problem in finite-dimensional normed spaces
• Vertex degrees of Steiner minimal trees in \(\ell_p^d\) and other smooth Minkowski spaces
• Flow-dependent networks: Existence and behavior at Steiner points
• Pseudo-Gilbert-Steiner trees

Cited In (5)

• Degenerate Gilbert—Steiner trees
• Angle-restricted Steiner arborescences for flow map layout
• Minimum cost flow‐dependent communication networks
• Around the Danzer problem and the construction of dense forests
• Flow-dependent networks: Existence and behavior at Steiner points

This page was built for publication: The Gilbert arborescence problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5326792)