The Gilbert arborescence problem

DOI10.1002/NET.21475MaRDI QIDQ5326792zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

Cites work

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

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)