Gradient-Constrained Minimum Networks. III. Fixed Topology

M. Brazil (), J. H. Rubinstein, D. A. Thomas, J. F. Weng and N. Wormald
Additional contact information
M. Brazil: The University of Melbourne
J. H. Rubinstein: The University of Melbourne
D. A. Thomas: The University of Melbourne
J. F. Weng: The University of Melbourne
N. Wormald: University of Waterloo

Journal of Optimization Theory and Applications, 2012, vol. 155, issue 1, No 19, 336-354

Abstract: Abstract The gradient-constrained Steiner tree problem asks for a shortest total length network interconnecting a given set of points in 3-space, where the length of each edge of the network is determined by embedding it as a curve with absolute gradient no more than a given positive value m, and the network may contain additional nodes known as Steiner points. We study the problem for a fixed topology, and show that, apart from a few easily classified exceptions, if the positions of the Steiner points are such that the tree is not minimum for the given topology, then there exists a length reducing perturbation that moves exactly 1 or 2 Steiner points. In the conclusion, we discuss the application of this work to a heuristic algorithm for solving the global problem (across all topologies).

Keywords: Gradient constraint; Steiner trees; Minimum networks; Optimization (search for similar items in EconPapers)
Date: 2012
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-012-0036-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:155:y:2012:i:1:d:10.1007_s10957-012-0036-3

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-012-0036-3

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().