Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Euclidean and Minkowski Steiner Trees Read chapter Read first chapter

2015 | OriginalPaper | Chapter

4. Steiner Trees with Other Cost Functions and Constraints

Authors : Marcus Brazil, Martin Zachariasen

Published in: Optimal Interconnection Trees in the Plane

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this chapter we look at Steiner tree problems that involve other cost functions and constraints (beyond those discussed in the first three chapters) but that still can be solved exactly by exploiting the geometric properties of minimal solutions. We focus particularly on four types of Steiner tree problems: the gradient-constrained Steiner tree problem, which serves as another example of an exactly solvable Steiner tree problem in a Minkowski plane with useful applications; the obstacle-avoiding Steiner tree problem, which is an important variation of the Steiner tree problem with applications in the physical design of microchips; bottleneck and other k-Steiner tree problems, where there is a given bound on the number of Steiner points; and Steiner tree problems optimising a cost associated with flow on the network.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Rectilinear Steiner Trees
next chapter Steiner Trees in Graphs and Hypergraphs
Footnotes
1
This background on mining, which focusses on hard rock mines containing metallic deposits, is drawn primarily from [8] and [48]. For a more comprehensive introduction to the infrastructure of an underground mine see [186].
 
2
Some examples of the many heuristic approaches developed for the rectilinear obstacle-avoiding Steiner tree problem include the algorithms of Lin et al. [258], Long et al. [267], Li and Young [254], Liu et al. [262] and Ajwani et al. [5]. The last of these makes use of the FLUTE algorithm, described in Sect. 3.​4 Also of note is a graph-based approximation algorithm for the octilinear obstacle-avoiding Steiner tree problem proposed by Müller-Hannemann and Schulze [288].
 
3
For the equivalent result to Lemma 4.8 in the Euclidean plane, see for example [345].
 
4
One of the most important early references on the Euclidean problem with polygonal obstacles is the paper of Provan [317] on approximation schemes for this problem. Other early papers relating to the Euclidean problem include [350] and [391]. The key papers on algorithmic approaches to solving the exact problem are those of Winter [403] and Zachariasen and Winter [433].
 
5
Although numerous heuristics for the rectilinear minimum obstacle-avoiding Steiner tree problem have been developed, the literature on exact solutions is rather sparse. The first substantial results appear to be those of Ganley and Cohoon [163], who developed algorithms for solving instances with up to four terminals, using the so-called escape graph. More recently, Huang et al. [204, 208] presented a GeoSteiner-type algorithm able, in theory, to exactly solve instances of arbitrary size, using an approach similar to the one developed in this section. These methods were further refined and discussed by Juhl [225]. We note, however, that all of these previous results assume that the polygonal obstacles have boundary edges using only legal orientations, whereas we make no restrictions on the orientations of the boundary edges of obstacles in this section.
 
6
A slightly weaker version of this result has appeared in the literature, but only for the rectilinear Steiner tree problem, with rectilinear obstacles; see [205, 206, 208] and [225].
 
7
This application was first suggested by David Lee in his unpublished paper, ‘Some industrial case studies of Steiner trees’ presented at the NATO Advanced Research Workshop, ‘Topological Network Design: Analysis and Synthesis’, in Copenhagen, 1989.
 
8
The bottleneck Steiner tree problem was first proposed by Chiang et al. [96] in the context of Steiner trees in graphs, and was originally known as the Steiner min-max tree problem. There it was shown that this problem has a simple polynomial-time algorithm, in terms of the number of vertices and edges of the entire graph. However, in terms of the cardinality of the terminal set, Berman and Zelikovsky [28] have shown that the problem does not admit any polynomial-time approximation algorithm with performance ratio less than 2 unless P = NP. The Euclidean version of the geometric bottleneck k-Steiner tree problem in the plane, as defined in this chapter, was first studied by Du et al. in [139] and [384]. A survey of the results in this area up to 2008, with a focus on approximation algorithms, can be found in Chapter 6 of [134].
 
9
The algorithm developed in Sect. 4.3 for the general k-Steiner tree problem can in theory apply to a wider range of norms than the PE norms. The algorithm for these other norms will, however, be difficult to implement in practice. The precise required properties of the widest class of norms for which the algorithm can apply are given in [52].
 
10
Note that [21] gives a slightly weaker version of condition 3, the bound on the degree of Steiner points; in particular, for ℓ 1 and ℓ ∞ an upper bound of 7 rather than 5 is given. The bounds in [21] are based on the Hadwiger numbers of the unit balls, that is, the largest number of non-overlapping translates of the unit ball that can be brought into contact with it. However, for ℓ 1 and ℓ ∞ (each of which have polygonal unit balls) a tighter bound can be found by using Lemma 4.22 together with the arguments of Monma and Suri in [285].
 
11
This paper actually predates Gilbert’s seminal paper with Henry Pollak [179] on the Euclidean Steiner tree problem.
 
12
The problem of constructing a Steiner point in the weighted case (i.e., the weighted Fermat-Torricelli problem) was first solved, for the Euclidean plane, by Weber [390] in 1909. More details on the history and mathematics behind the general weighted Fermat-Torricelli problem (for Steiner points of degree ≥ 3) can be found in the surveys of Wesolowsky [396] and Kupitz and Martini [240]. A recent treatment of the Euclidean weighted Fermat-Torricelli problem for Steiner points of degree 3 can be found in a paper of Jalal and Krarup [222], where the problem is referred to as FERPOS.
 
13
Ptolemy’s theorem is named after the Greek astronomer and mathematician Claudius Ptolemaeus, who stated and used the result in about AD 150. Jalal and Krarup [222] prove Theorem 4.37 without the use of Ptolemy’s theorem, and are then able to obtain Ptolemy’s theorem as a simple corollary.
 
14
Note that in [124], condition (W3b), the subadditivity condition, was incorrectly interpreted as concavity of the cost function.
 
15
The formulation and solution of a hierarchical network design problem in which there are at least two grades of service dates back to a 1986 paper of Current et al. [126]. The first study of the grade of service Steiner tree problem, where the grades of service on the edges are determined by weights on the terminals, was a paper by Colbourn and Xue in 2000 [116], although this was for the Steiner tree problem in graphs. The main study of the geometric version of this problem is the paper of Xue et al. [416]. Note that our formulation of the Euclidean grade of service Steiner tree problem in the plane slightly simplifies that given in [416].
 
16
The former of these two methods of bounding the number of Steiner points is the most popular in the literature, and is employed in [160, 166, 355] and [28] amongst others. The second method is particularly relevant to applications surrounding the modelling of wireless sensor network deployment; see for example [412] and [413]. Both methods are also discussed in [57].
 
Literature
2.
Abellanas, M., Hurtado, F., Icking, C., Klein, R., Langetepe, E., Ma, L., Palop, B., Sacristán, V.: The farthest color Voronoi diagram and related problems. Technical report, Department of Computer Science I, University of Bonn (2006)
5.
Ajwani, G., Chu, C., Mak, W.-K.: FOARS: FLUTE based obstacle-avoiding rectilinear Steiner tree construction. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 30(2), 194–204 (2011)CrossRef
8.
Alford, C., Brazil, M., Lee, D.H.: Optimisation in underground mining. In: Weintraub, A., Romero, C., Bjørndal, T., Epstein, R. (eds.) Handbook of Operations Research in Natural Resources, pp. 561–577. Springer, New York (2007)
17.
18.
Aurenhammer, F., Klein, R.: Voronoi diagrams. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, chapter 5, pp. 201–290. North-Holland, Amsterdam (2000)CrossRef
21.
Bae, S.W., Choi, S., Lee, C., Tanigawa, S.: Exact algorithms for the bottleneck Steiner tree problem. Algorithmica 61(4), 924–948 (2011)CrossRefMATHMathSciNet
22.
Bae, S.W., Lee, C., Choi, S.: On exact solutions to the Euclidean bottleneck Steiner tree problem. Inf. Process. Lett. 110(16), 672–678 (2010)CrossRefMATHMathSciNet
23.
Bainbridge, S., Eggeling, D., Page, G.: Lessons from the field – two years of deploying operational wireless sensor networks on the Great Barrier Reef. Sensors 11(7), 6842–6855 (2011)CrossRef
28.
Berman, P., Zelikovsky, A.: On approximation of the power-p and bottleneck Steiner trees. In: Du, D.-Z., Smith, J.M., Rubinstein, J.H. (eds.) Advances in Steiner Trees. Combinatorial Optimization, vol. 6, pp. 117–135. Springer, New York (2000)CrossRef
32.
Bienstock, D., Brickell, E.F., Monma, C.L.: On the structure of minimum-weight k-connected spanning networks. SIAM J. Discret. Math. 3(3), 320–329 (1990)CrossRefMATHMathSciNet
37.
Borah, M., Owens, R.M., Irwin, M.J.: An edge-based heuristic for Steiner routing. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 13, 1563–1568 (1994)CrossRef
48.
Brazil, M., Grossman, P.A., Lee, D.H., Rubinstein, J.H., Thomas, D.A., Wormald, N.C.: Constrained path optimisation for underground mine layout. In: World Congress on Engineering 2007, London, pp. 856–861 (2007)
49.
Brazil, M., Lee, D.H., Rubinstein, J.H., Thomas, D.A., Weng, J.F., Wormald, N.C.: Network optimisation of underground mine design. Proc. Australas. Inst. Min. Metall. 305(1), 57–66 (2000)
50.
Brazil, M., Lee, D.H., Van Leuven, M., Rubinstein, J.H., Thomas, D.A., Wormald, N.C.: Optimising declines in underground mines. Min. Technol. 112(3), 164–170 (2003)CrossRef
51.
Brazil, M., Nielsen, B.K., Winter, P., Zachariasen, M.: Rotationally optimal spanning and Steiner trees in uniform orientation metrics. Comput. Geom. Theory Appl. 29, 251–263 (2004)CrossRefMATHMathSciNet
52.
Brazil, M., Ras, C.J., Swanepoel, K.J., Thomas, D.A.: Generalised k-Steiner tree problems in normed planes. Algorithmica 71(1), 66–86 (2015)CrossRefMATHMathSciNet
53.
Brazil, M., Ras, C.J., Thomas, D.A.: Approximating minimum Steiner point trees in Minkowski planes. Networks 56(4), 244–254 (2010)CrossRefMATHMathSciNet
54.
Brazil, M., Ras, C.J., Thomas, D.A.: The bottleneck 2-connected k-Steiner network problem for k ≤ 2. Discret. Appl. Math. 160(7), 1028–1038 (2012)CrossRefMATHMathSciNet
55.
Brazil, M., Ras, C.J., Thomas, D.A.: Relay augmentation for lifetime extension of wireless sensor networks. IET Wirel. Sens. Syst. 3(2), 145–152 (2013)CrossRef
56.
Brazil, M., Ras, C.J., Thomas, D.A.: An exact algorithm for the bottleneck 2-connected k-Steiner network problem in L p planes. arXiv preprint arXiv:1111.2105 (2014)
57.
Brazil, M., Ras, C.J., Thomas, D.A.: A flow-dependent quadratic Steiner tree problem in the Euclidean plane. Networks 64(1), 18–28 (2014)CrossRefMathSciNet
60.
Brazil, M., Rubinstein, J.H., Thomas, D.A., Weng, J.F., Wormald, N.C.: Gradient-constrained minimum networks. I. Fundamentals. J. Global Optim. 21(2), 139–155 (2001)CrossRefMATHMathSciNet
61.
Brazil, M., Rubinstein, J.H., Thomas, D.A., Weng, J.F., Wormald, N.C.: Gradient-constrained minimum networks. III. Fixed topology. J. Optim. Theory Appl. 155(1), 336–354 (2012)CrossRefMATHMathSciNet
63.
Brazil, M., Thomas, D.A., Weng, J.F.: Gradient constrained minimal Steiner trees. In: Pardalas, P.M., Du, D.-Z. (eds.) Network Design: Connectivity and Facilities Location (DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 40). American Mathematical Society, Providence, Rhode Island (1998)
66.
69.
Brazil, M., Thomas, D.A., Weng, J.F.: Gradient-constrained minimum networks (II). Labelled or locally minimal Steiner points. J. Global Optim. 42(1), 23–37 (2008)MATHMathSciNet
71.
Brazil, M., Volz, M.G.: Gradient-constrained minimum interconnection networks. In: Pardalos, P.M., Du, D.Z., Graham, R.L. (eds.) Handbook of Combinatorial Optimization, pp. 1459–1510. Springer, New York (2013)CrossRef
74.
79.
Cavendish, J.C.: Automatic triangulation of arbitrary planar domains for the finite element method. Int. J. Numer. Methods Eng. 8(4), 679–696 (1974)CrossRefMATH
84.
Chen, D., Du, D.-Z., Hu, X.-D., Lin, G.-H., Wang, L., Xue, G.: Approximations for Steiner trees with minimum number of Steiner points. J. Global Optim. 18(1), 17–33 (2000)CrossRefMATHMathSciNet
93.
Cheng, X., Du, D.-Z., Wang, L., Xu, B.: Relay sensor placement in wireless sensor networks. Wirel. Netw. 14(3), 347–355 (2008)CrossRef
94.
Chew, L.P., Drysdale III, R.L.: Voronoi diagrams based on convex distance function. In: Proceedings of the First Annual ACM Symposium on Computational Geometry (SCG), New York, pp. 235–244 (1985)
96.
Chiang, C., Sarrafzadeh, M., Wong, C.K.: Global routing based on Steiner min-max trees. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 9, 1318–1325 (1990)CrossRef
114.
116.
Colbourn, C.J., Xue, G.: Grade of service Steiner trees in series-parallel networks. In: Du, D.-Z., Smith, J.M., Rubinstein, J.H. (eds) Advances in Steiner Trees, pp. 163–174. Kluwer Academic Publishers, Dordrecht (2000)CrossRef
117.
Colthurst, T., Cox, C., Foisy, J., Howards, H., Kollett, K., Lowy, H., Root, S.: Networks minimizing length plus the number of Steiner points. In: Du, D.-Z., Pardalos, P.M. (eds.) Network Optimization Problems: Algorithms, Applications and Complexity, pp. 23–36. World Scientific, Singapore (1993)CrossRef
124.
125.
Coxeter, H.S.M.: Introduction to Geometry. Wiley, New York (1969)MATH
126.
Current, J.R., ReVelle, C.S., Cohon, J.L.: The hierarchical network design problem. Eur. J. Oper. Res. 27(1), 57–66 (1986)CrossRefMATH
130.
132.
Drezner, Z., Wesolowsky, G.O.: A new method for the multifacility minimax location problem. J. Oper. Res. Soc. 29(11), 1095–1101 (1978)CrossRefMATHMathSciNet
134.
Du, D.-Z., Hu, X.-D.: Steiner Tree Problems in Computer Communication Networks. World Scientific, Singapore (2008)CrossRefMATH
139.
Du, D.-Z., Wang, L., Xu, B.: The Euclidean bottleneck Steiner tree and Steiner tree with minimum number of Steiner points. In: Wang, J. (ed.) Computing and Combinatorics, pp. 509–518. Springer, New York (2001)CrossRef
149.
Elzinga, J., Hearn, D., Randolph, W.D.: Minimax multifacility location with Euclidean distances. Transp. Sci. 10(4), 321–336 (1976)CrossRefMathSciNet
160.
Ganley, J.L.: Geometric interconnection and placement algorithms. PhD thesis, The University of Virginia (1995)
163.
Ganley, J.L., Cohoon, J.P.: Routing a multi-terminal critical net: Steiner tree construction in the presence of obstacles. In: IEEE Proceedings of the International Symposium on Circuits and Systems, London, pp. 113–116 (1994)
165.
166.
Ganley, J.L., Salowe, J.S.: The power-p Steiner tree problem. Nord. J. Comput. 5(2), 115–127 (1998)MATHMathSciNet
172.
177.
178.
Gilbert, E.N.: Minimum cost communication networks. Bell Syst. Tech. J. 46, 2209–2227 (1967)CrossRef
179.
186.
Hamrin, H.: Underground mining methods and applications. In: Hustrilid, W.A., Bullock, R.L. (eds.) Underground Mining Methods. Society for Mining, Metallurgy, and Exploration, Littleton, Colorado (2001)
204.
Huang, T., Li, L., Young, E.F.Y.: On the construction of optimal obstacle-avoiding rectilinear Steiner minimum trees. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 30(5), 718–731 (2011)CrossRef
205.
Huang, T., Young, E.F.Y.: Obstacle-avoiding rectilinear Steiner minimum tree construction: an optimal approach. In: Proceedings ACM International Conference on Computer-Aided Design (ICCAD), San Jose, pp. 610–613 (2010)
206.
Huang, T., Young, E.F.Y.: An exact algorithm for the construction of rectilinear Steiner minimum trees among complex obstacles. In: Proceedings of the 48th ACM/IEEE Design Automation Conference (DAC), San Diego, pp. 164–169 (2011)
208.
Huang, T., Young, E.F.Y.: Obsteiner: an exact algorithm for the construction of rectilinear Steiner minimum trees in the presence of complex rectilinear obstacles. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 32(6), 882–893 (2013)CrossRef
212.
222.
225.
Juhl, D.D.: Full Steiner trees for the obstacle-avoiding rectilinear Steiner tree problem. Master’s thesis, Department of Computer Science, University of Copenhagen (2013)
228.
Kahng, A.B., Robins, G.: A new class of iterative Steiner tree heuristics with good performance. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 11(7), 893–902 (1992)CrossRef
230.
Karl, H., Willig, A.: Protocols and Architectures for Wireless Sensor Networks. Wiley, New York (2007)
237.
Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms. Algorithms and Combinatorics, 4th edn. Springer, Berlin (2008)
240.
Kupitz, Y.S., Martini, H.: Geometric aspects of the generalized Fermat-Torricelli problem. In: Barany, I., Boroczky, K. (eds.) Bolyai Society Mathematical Studies, 6: Intuitive Geometry, pp. 55–127. Janos Bolyai Mathematical Society, Budapest (1997)
247.
Lee, J.: A first course in combinatorial optimization. Cambridge Texts in Applied Mathematics. Cambridge University Press, Cambridge (2004)CrossRefMATH
250.
Lerchs, H., Grossmann, I.F.: Optimum design of open-pit mines. Trans. Can. Inst. Min. Metall. Pet. 68, 17–24 (1965)
253.
Li, C.-S., Tong, F.F.-K., Georgiou, C.J., Chen, M.: Gain equalization in metropolitan and wide area optical networks using optical amplifiers. In: Proceedings of the 13th IEEE Conference on Computer Communications: Networking for Global Communications (INFOCOM), Toronto, pp. 130–137 (1994)
254.
Li, L., Young, E.F.: Obstacle-avoiding rectilinear Steiner tree construction. In: Proceedings ACM International Conference on Computer-Aided Design (ICCAD), San Jose, pp. 523–528 (2008)
258.
Lin, C.-W., Chen, S.-Y., Li, C.-F., Chang, Y.-W., Yang, C.-L.: Obstacle-avoiding rectilinear Steiner tree construction based on spanning graphs. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 27(4), 643–653 (2008)CrossRef
260.
Lin, G.-H., Xue, G.: Steiner tree problem with minimum number of Steiner points and bounded edge-length. Inf. Process. Lett. 69(2), 53–57 (1999)CrossRefMathSciNet
262.
Liu, C.-H., Kuo, S.-Y., Lee, D.T., Lin, C.-S., Weng, J.-H., Yuan, S.-Y.: Obstacle-avoiding rectilinear Steiner tree construction: a Steiner-point-based algorithm. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 31(7), 1050–1060 (2012)CrossRef
267.
Long, J., Zhou, H., Memik, S.O.: EBOARST: an efficient edge-based obstacle-avoiding rectilinear Steiner tree construction algorithm. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 27(12), 2169–2182 (2008)CrossRef
269.
Lu, B., Gu, J., Hu, X., Shragowitz, E.: Wire segmenting for buffer insertion based on RSTP-MSP. Theor. Comput. Sci. 262(1), 257–267 (2001)CrossRefMATHMathSciNet
272.
Măndoiu, I.I., Zelikovsky, A.Z.: A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points. Inf. Process. Lett. 75(4), 165–167 (2000)CrossRefMATH
285.
288.
Müller-Hannemann, M., Schulze, A.: Hardness and approximation of octilinear Steiner trees. Int. J. Comput. Geom. Appl. 17, 231–260 (2007)CrossRefMATH
292.
Newman, A.M., Rubio, E., Caro, R., Weintraub, A., Eurek, K.: A review of operations research in mine planning. Interfaces 40(3), 222–245 (2010)CrossRef
295.
Nielsen, B.K., Winter, P., Zachariasen, M.: Rectilinear trees under rotation and related problems. In: Proceedings of the 18th European Workshop on Computational Geometry, Warsaw, pp. 18–22 (2002)
296.
Okabe, A., Boots, B., Sugihara, K., Chiu, S.N.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd edn. Wiley, New York (1995)
297.
Oppermann, F.J., Boano, C.A., Römer, K.: A decade of wireless sensing applications: survey and taxonomy. In: Ammari, H.M. (ed.) The Art of Wireless Sensor Networks, pp. 11–50. Springer, Heidelberg (2014)CrossRef
317.
319.
Ramamurthy, B., Iness, J., Mukherjee, B.: Minimizing the number of optical amplifiers needed to support a multi-wavelength optical LAN/MAN. In: Proceedings of INFOCOM’97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, Kobe, vol. 1, pp. 261–268 (1997)
328.
Rubinstein, J.H., Thomas, D.A., Weng, J.F.: Degree-five Steiner points cannot reduce network costs for planar sets. Networks 22(6), 531–537 (1992)CrossRefMATHMathSciNet
337.
343.
344.
Shang, S., Hu, X., Jing, T.: Rotational Steiner ratio problem under uniform orientation metrics. In: Discrete Geometry, Combinatorics and Graph Theory. Lecture Notes in Computer Science, vol. 4381, pp. 166–176. Springer, Berlin/Heidelberg (2007)
345.
350.
Smith, J.M., Liebman, J.S.: Steiner trees, Steiner circuits and the interference problem in building design. Eng. Optim. 4, 15–36 (1979)
351.
355.
358.
363.
Thomas, D.A., Brazil, M., Lee, D.H., Wormald, N.C.: Network modelling of underground mine layout: two case studies. Int. Trans. Oper. Res. 14(2), 143–158 (2007)CrossRefMATH
365.
374.
376.
Volz, M.G.: Gradient-constrained flow-dependent networks for underground mine design. PhD thesis, The University of Melbourne (2008)
377.
Volz, M.G., Brazil, M., Ras, C.J., Swanepoel, K.J., Thomas, D.A.: The Gilbert arborescence problem. Networks 61(3), 238–247 (2013)CrossRefMATHMathSciNet
383.
Wang, F., Wang, D., Liu, J.: Traffic-aware relay node deployment for data collection in wireless sensor networks. In: 6th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON’09), Rome, pp. 1–9 (2009)
384.
390.
Weber, A.: Über den Standort der Industrien. Teil I: Reine Theorie des Standorts. Verlag J. C. B. Mohr (1909). Translated by C. J. Friedrich as Alfred Weber’s Theory of the Location of Industries. Chicago University Press, Chicago, 1929
391.
392.
393.
Weng, J.F.: Minimum networks for separating and surrounding objects. In: Cheng, X., Du, D.-Z. (eds.) Steiner Trees in Industry. Combinatorial Optimization, vol. 11, pp. 427–439. Springer, New York (2001)CrossRef
394.
Weng, J.F.: Generalized Melzak’s construction in the Steiner tree problem. Int. J. Comput. Geom. Appl. 12(6), 481–488 (2002)CrossRefMATH
395.
396.
Wesolowsky, G.O.: The Weber problem: history and perspectives. Locat. Sci. 1, 5–23 (1993)MATH
403.
Winter, P.: Euclidean Steiner minimal trees with obstacles and Steiner visibility graphs. Discret. Appl. Math. 47, 187–206 (1993)CrossRefMATH
406.
Winter, P., Smith, J.M.: Steiner minimal trees for three points with one convex polygonal obstacle. Ann. Oper. Res. 33, 577–599 (1991)CrossRefMATHMathSciNet
412.
Xin, Y., Guven, T., Shayman, M.: Relay deployment and power control for lifetime elongation in sensor networks. In: IEEE International Conference on Communications, Istanbul, vol. 8, pp. 3461–3466 (2006)
413.
Xu, K., Hassanein, H., Takahara, G., Wang, Q.: Relay node deployment strategies in heterogeneous wireless sensor networks. IEEE Trans. Mob. Comput. 9(2), 145–159 (2010)CrossRef
414.
Xue, G.: A branch-and-bound algorithm for computing node weighted Steiner minimum trees. In: Jiang, T., Lee, D.T. (eds.) Computing and Combinatorics. Lecture Notes in Computer Science, vol. 1276, pp. 383–392. Springer, Berlin/Heidelberg (1997)
416.
Xue, G., Lin, G.-H., Du, D.-Z.: Grade of service Steiner minimum trees in the Euclidean plane. Algorithmica 31, 479–500 (2004)CrossRefMathSciNet
433.
Zachariasen, M., Winter, P.: Obstacle-avoiding Euclidean Steiner trees in the plane: an exact algorithm. In: Workshop on Algorithm Engineering and Experimentation (ALENEX), Baltimore. Lecture Notes in Computer Science 1619, pp. 282–295. Springer, Berlin/Heidelberg (1999)
Metadata
Title
Steiner Trees with Other Cost Functions and Constraints
Authors
Marcus Brazil
Martin Zachariasen
Copyright Year
2015
Book
Optimal Interconnection Trees in the Plane

Print ISBN: 978-3-319-13914-2

Electronic ISBN: 978-3-319-13915-9

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-13915-9_4

Premium Partner

    Image Credits