Relevant bibliographies by topics / Steiner problem / Journal articles
To see the other types of publications on this topic, follow the link: Steiner problem.

Journal articles on the topic 'Steiner problem'

Author: Grafiati
Published: 4 June 2021
Last updated: 21 February 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Steiner problem.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Weng, Jia Feng. "Steiner polygons in the Steiner problem." Geometriae Dedicata 52, no. 2 (September 1994): 119–27. http://dx.doi.org/10.1007/bf01263600.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Sharma, Gokarna, and Costas Busch. "The Bursty Steiner Tree Problem." International Journal of Foundations of Computer Science 28, no. 07 (November 2017): 869–87. http://dx.doi.org/10.1142/s0129054117500290.

Full text
Abstract:
We introduce and study a new Steiner tree problem variation called the bursty Steiner tree problem where new nodes arrive into bursts. This is an online problem which becomes the well-known online Steiner tree problem if the number of nodes in each burst is exactly one and becomes the classic Steiner tree problem if all the nodes appear in a single burst. In undirected graphs, we provide a tight bound of [Formula: see text] on the competitive ratio for this problem, where [Formula: see text] is the total number of nodes to be connected and [Formula: see text] is the total number of different bursts. In directed graphs of bounded edge asymmetry [Formula: see text], we provide a competitive ratio for this problem with a gap of [Formula: see text] factor between the lower bound and the upper bound. We also show that a tight bound of [Formula: see text] on the competitive ratio can be obtained for a bursty variation of the terminal Steiner tree problem. These are the first results that provide clear performance trade-offs for a novel Steiner tree problem variation that subsumes both of its online and classic versions.
APA, Harvard, Vancouver, ISO, and other styles
3

Vujosevic, Mirko, and Milan Stanojevic. "A bicriterion Steiner tree problem on graph." Yugoslav Journal of Operations Research 13, no. 1 (2003): 25–33. http://dx.doi.org/10.2298/yjor0301025v.

Full text
Abstract:
This paper presents a formulation of bicriterion Steiner tree problem which is stated as a task of finding a Steiner tree with maximal capacity and minimal length. It is considered as a lexicographic multicriteria problem. This means that the bottleneck Steiner tree problem is solved first. After that, the next optimization problem is stated as a classical minimums Steiner tree problem under the constraint on capacity of the tree. The paper also presents some computational experiments with the multicriteria problem.
APA, Harvard, Vancouver, ISO, and other styles
4

Chen, Yen Hung. "The Clustered Selected-Internal Steiner Tree Problem." International Journal of Foundations of Computer Science 33, no. 01 (November 30, 2021): 55–66. http://dx.doi.org/10.1142/s0129054121500362.

Full text
Abstract:
Given a complete graph [Formula: see text], with nonnegative edge costs, two subsets [Formula: see text] and [Formula: see text], a partition [Formula: see text] of [Formula: see text], [Formula: see text], [Formula: see text] and [Formula: see text] of [Formula: see text], [Formula: see text], a clustered Steiner tree is a tree [Formula: see text] of [Formula: see text] that spans all vertices in [Formula: see text] such that [Formula: see text] can be cut into [Formula: see text] subtrees [Formula: see text] by removing [Formula: see text] edges and each subtree [Formula: see text] spans all vertices in [Formula: see text], [Formula: see text]. The cost of a clustered Steiner tree is defined to be the sum of the costs of all its edges. A clustered selected-internal Steiner tree of [Formula: see text] is a clustered Steiner tree for [Formula: see text] if all vertices in [Formula: see text] are internal vertices of [Formula: see text]. The clustered selected-internal Steiner tree problem is concerned with the determination of a clustered selected-internal Steiner tree [Formula: see text] for [Formula: see text] and [Formula: see text] in [Formula: see text] with minimum cost. In this paper, we present the first known approximation algorithm with performance ratio [Formula: see text] for the clustered selected-internal Steiner tree problem, where [Formula: see text] is the best-known performance ratio for the Steiner tree problem.
APA, Harvard, Vancouver, ISO, and other styles
5

Gueron, Shay, and Ran Tessler. "The Fermat-Steiner Problem." American Mathematical Monthly 109, no. 5 (May 2002): 443. http://dx.doi.org/10.2307/2695644.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Imase, Makoto, and Bernard M. Waxman. "Dynamic Steiner Tree Problem." SIAM Journal on Discrete Mathematics 4, no. 3 (August 1991): 369–84. http://dx.doi.org/10.1137/0404033.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Borndörfer, Ralf, Marika Karbstein, and Marc E. Pfetsch. "The Steiner connectivity problem." Mathematical Programming 142, no. 1-2 (June 8, 2012): 133–67. http://dx.doi.org/10.1007/s10107-012-0564-5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Gueron, Shay, and Ran Tessler. "The Fermat-Steiner Problem." American Mathematical Monthly 109, no. 5 (May 2002): 443–51. http://dx.doi.org/10.1080/00029890.2002.11919871.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

van Oudheusden, Dirk. "The Steiner tree problem." European Journal of Operational Research 81, no. 1 (February 1995): 221. http://dx.doi.org/10.1016/0377-2217(95)90155-8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

WENG, J. F., I. MAREELS, and D. A. THOMAS. "COMPUTING STEINER POINTS AND PROBABILITY STEINER POINTS IN ℓ1 AND ℓ2 METRIC SPACES." Discrete Mathematics, Algorithms and Applications 01, no. 04 (December 2009): 541–54. http://dx.doi.org/10.1142/s1793830909000403.

Full text
Abstract:
The Steiner tree problem is a well known network optimization problem which asks for a connected minimum network (called a Steiner minimum tree) spanning a given point set N. In the original Steiner tree problem the given points lie in the Euclidean plane or space, and the problem has many variants in different applications now. Recently a new type of Steiner minimum tree, probability Steiner minimum tree, is introduced by the authors in the study of phylogenies. A Steiner tree is a probability Steiner tree if all points in the tree are probability vectors in a vector space. The points in a Steiner minimum tree (or a probability Steiner tree) that are not in the given point set are called Steiner points (or probability Steiner points respectively). In this paper we investigate the properties of Steiner points and probability Steiner points, and derive the formulae for computing Steiner points and probability Steiner points in ℓ1- and ℓ2-metric spaces. Moreover, we show by an example that the length of a probability Steiner tree on 3 points and the probability Steiner point in the tree are smooth functions with respect to p in d-space.
APA, Harvard, Vancouver, ISO, and other styles
11

MÜLLER-HANNEMANN, MATTHIAS, and ANNA SCHULZE. "HARDNESS AND APPROXIMATION OF OCTILINEAR STEINER TREES." International Journal of Computational Geometry & Applications 17, no. 03 (June 2007): 231–60. http://dx.doi.org/10.1142/s021819590700232x.

Full text
Abstract:
Given a point set K of terminals in the plane, the octilinear Steiner tree problem is to find a shortest tree that interconnects all terminals and edges run either in horizontal, vertical, or ±45° diagonal direction. This problem is fundamental for the novel octilinear routing paradigm in VLSI design, the so-called X-architecture. As the related rectilinear and the Euclidian Steiner tree problem are well-known to be NP-hard, the same was widely believed for the octilinear Steiner tree problem but left open for quite some time. In this paper, we prove the NP-completeness of the decision version of the octilinear Steiner tree problem. We also show how to reduce the octilinear Steiner tree problem to the Steiner tree problem in graphs of polynomial size with the following approximation guarantee. We construct a planar graph of size [Formula: see text] which contains a (1 + ε)–approximation of a minimum octilinear Steiner tree for every ε > 0 and n = |K|. Hence, we can apply any α–approximation algorithm for the Steiner tree problem in graphs (for planar graphs, Borradaile et al. very recently presented a polynomial time approximation scheme) and achieve an (α + ε)–approximation bound for the octilinear Steiner tree problem. This approximation guarantee also holds for the more difficult case where the Steiner tree has to avoid blockages (obstacles bounded by octilinear polygons).
APA, Harvard, Vancouver, ISO, and other styles
12

Yang, Zong-Xiao, Xiao-Yao Jia, Jie-Yu Hao, and Yan-Ping Gao. "Geometry-Experiment Algorithm for Steiner Minimal Tree Problem." Journal of Applied Mathematics 2013 (2013): 1–10. http://dx.doi.org/10.1155/2013/367107.

Full text
Abstract:
It is well known that the Steiner minimal tree problem is one of the classical nonlinear combinatorial optimization problems. A visualization experiment approach succeeds in generating Steiner points automatically and showing the system shortest path, named Steiner minimum tree, physically and intuitively. However, it is difficult to form stabilized system shortest path when the number of given points is increased and irregularly distributed. Two algorithms, geometry algorithm and geometry-experiment algorithm (GEA), are constructed to solve system shortest path using the property of Delaunay diagram and basic philosophy of Geo-Steiner algorithm and matching up with the visualization experiment approach (VEA) when the given points increase. The approximate optimizing results are received by GEA and VEA for two examples. The validity of GEA was proved by solving practical problems in engineering, experiment, and comparative analysis. And the global shortest path can be obtained by GEA successfully with several actual calculations.
APA, Harvard, Vancouver, ISO, and other styles
13

Mackinnon, Nick. "74.25 The Steiner Grid Problem." Mathematical Gazette 74, no. 468 (June 1990): 161. http://dx.doi.org/10.2307/3619370.

Full text
APA, Harvard, Vancouver, ISO, and other styles
14

Ferone, Daniele, Paola Festa, and Francesca Guerriero. "The Rainbow Steiner Tree Problem." Computers & Operations Research 139 (March 2022): 105621. http://dx.doi.org/10.1016/j.cor.2021.105621.

Full text
APA, Harvard, Vancouver, ISO, and other styles
15

Lu, Chin Lung, Chuan Yi Tang, and Richard Chia-Tung Lee. "The full Steiner tree problem." Theoretical Computer Science 306, no. 1-3 (September 2003): 55–67. http://dx.doi.org/10.1016/s0304-3975(03)00209-3.

Full text
APA, Harvard, Vancouver, ISO, and other styles
16

Awerbuch, Baruch, Yossi Azar, and Yair Bartal. "On-line generalized Steiner problem." Theoretical Computer Science 324, no. 2-3 (September 2004): 313–24. http://dx.doi.org/10.1016/j.tcs.2004.05.021.

Full text
APA, Harvard, Vancouver, ISO, and other styles
17

Georgakopoulos, George, and Christos H. Papadimitriou. "The 1-steiner tree problem." Journal of Algorithms 8, no. 1 (March 1987): 122–30. http://dx.doi.org/10.1016/0196-6774(87)90032-0.

Full text
APA, Harvard, Vancouver, ISO, and other styles
18

Rao, Sailesh K., P. Sadayappan, Frank K. Hwang, and Peter W. Shor. "The rectilinear steiner arborescence problem." Algorithmica 7, no. 1-6 (June 1992): 277–88. http://dx.doi.org/10.1007/bf01758762.

Full text
APA, Harvard, Vancouver, ISO, and other styles
19

Gassner, Elisabeth. "The Steiner Forest Problem revisited." Journal of Discrete Algorithms 8, no. 2 (June 2010): 154–63. http://dx.doi.org/10.1016/j.jda.2009.05.002.

Full text
APA, Harvard, Vancouver, ISO, and other styles
20

Chekuri, Chandra, Sudipto Guha, and Joseph (Seffi) Naor. "The Steiner k-Cut Problem." SIAM Journal on Discrete Mathematics 20, no. 1 (January 2006): 261–71. http://dx.doi.org/10.1137/s0895480104445095.

Full text
APA, Harvard, Vancouver, ISO, and other styles
21

Winter, Pawel. "Steiner problem in Halin networks." Discrete Applied Mathematics 17, no. 3 (June 1987): 281–94. http://dx.doi.org/10.1016/0166-218x(87)90031-x.

Full text
APA, Harvard, Vancouver, ISO, and other styles
22

Rosenwein, Moshe B., and Richard T. Wong. "A constrained Steiner tree problem." European Journal of Operational Research 81, no. 2 (March 1995): 430–39. http://dx.doi.org/10.1016/0377-2217(93)e0245-s.

Full text
APA, Harvard, Vancouver, ISO, and other styles
23

Košťálek, Josef, and Pavla Koťátková Stránská. "MODIFIED STEINER-WEBER PROBLEM WITH ADDITIONAL RESTRICTIVE CONDITIONS." Acta academica karviniensia 18, no. 3 (September 30, 2018): 41–49. http://dx.doi.org/10.25142/aak.2018.019.

Full text
APA, Harvard, Vancouver, ISO, and other styles
24

Brazil, Marcus, Marcus Volz, Martin Zachariasen, Charl Ras, and Doreen Thomas. "New pruning rules for the Steiner tree problem and 2-connected Steiner network problem." Computational Geometry 78 (June 2019): 37–49. http://dx.doi.org/10.1016/j.comgeo.2018.10.003.

Full text
APA, Harvard, Vancouver, ISO, and other styles
25

Saikia, Parikshit, and Sushanta Karmakar. "Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE." International Journal of Foundations of Computer Science 31, no. 07 (November 2020): 941–68. http://dx.doi.org/10.1142/s0129054120500367.

Full text
Abstract:
The Steiner tree problem is one of the fundamental and classical problems in combinatorial optimization. In this paper we study this problem in the CONGESTED CLIQUE model (CCM) [29] of distributed computing. For the Steiner tree problem in the CCM, we consider that each vertex of the input graph is uniquely mapped to a processor and edges are naturally mapped to the links between the corresponding processors. Regarding output, each processor should know whether the vertex assigned to it is in the solution or not and which of its incident edges are in the solution. We present two deterministic distributed approximation algorithms for the Steiner tree problem in the CCM. The first algorithm computes a Steiner tree using [Formula: see text] rounds and [Formula: see text] messages for a given connected undirected weighted graph of [Formula: see text] nodes. Note here that [Formula: see text] notation hides polylogarithmic factors in [Formula: see text]. The second one computes a Steiner tree using [Formula: see text] rounds and [Formula: see text] messages, where [Formula: see text] and [Formula: see text] are the shortest path diameter and number of edges respectively in the given input graph. Both the algorithms achieve an approximation ratio of [Formula: see text], where [Formula: see text] is the number of leaf nodes in the optimal Steiner tree. For graphs with [Formula: see text], the first algorithm exhibits better performance than the second one in terms of the round complexity. On the other hand, for graphs with [Formula: see text], the second algorithm outperforms the first one in terms of the round complexity. In fact when [Formula: see text] then the second algorithm achieves a round complexity of [Formula: see text] and message complexity of [Formula: see text]. To the best of our knowledge, this is the first work to study the Steiner tree problem in the CCM.
APA, Harvard, Vancouver, ISO, and other styles
26

Lotarev, D. T., and A. P. Uzdemir. "Conversion of the Steiner Problem on the Euclidean Plane to the Steiner Problem on Graph." Automation and Remote Control 66, no. 10 (October 2005): 1603–13. http://dx.doi.org/10.1007/s10513-005-0194-y.

Full text
APA, Harvard, Vancouver, ISO, and other styles
27

BRAZIL, MARCUS, and MARTIN ZACHARIASEN. "THE UNIFORM ORIENTATION STEINER TREE PROBLEM IS NP-HARD." International Journal of Computational Geometry & Applications 24, no. 02 (June 2014): 87–105. http://dx.doi.org/10.1142/s0218195914500046.

Full text
Abstract:
Given a set of n points (known as terminals) and a set of λ ≥ 2 uniformly distributed (legal) orientations in the plane, the uniform orientation Steiner tree problem asks for a minimum-length network that interconnects the terminals with the restriction that the network is composed of line segments using legal orientations only. This problem is also known as the λ-geometry Steiner tree problem. We show that for any fixed λ > 2 the uniform orientation Steiner tree problem is NP-hard. In fact we prove a strictly stronger result, namely that the problem is NP-hard even when the terminals are restricted to lying on two parallel lines.
APA, Harvard, Vancouver, ISO, and other styles
28

Кукин, Валерий Дмитриевич, and Valery Kukin. "Optimization of Steiner trees search in the flow Steiner tree problem." Proceedings of the Karelian Research Centre of the Russian Academy of Sciences, no. 7 (June 26, 2018): 40. http://dx.doi.org/10.17076/mat816.

Full text
APA, Harvard, Vancouver, ISO, and other styles
29

WENG, JIA F. "GENERALIZED MELZAK'S CONSTRUCTION IN THE STEINER TREE PROBLEM." International Journal of Computational Geometry & Applications 12, no. 06 (December 2002): 481–88. http://dx.doi.org/10.1142/s0218195902000992.

Full text
Abstract:
For a given set of points in the Euclidean plane, a minimum network (a Steiner minimal tree) can be constructed using a geometric method, called Melzak's construction. The core of the Melzak construction is to replace a pair of terminals adjacent to the same Steiner point with a new terminal. In this paper we prove that the Melzak construction can be generalized to constructing Steiner minimal trees for circles so that either the given points (terminals) are constrained on the circles or the terminal edges are tangent to the circles. Then we show that the generalized Melzak construction can be used to find minimum networks separating and surrounding circular objects or to find minimum networks connecting convex and smoothly bounded objects and avoiding convex and smoothly bounded obstacles.
APA, Harvard, Vancouver, ISO, and other styles
30

Dong, Guan-Qiang, Zong-Xiao Yang, Lei Song, Kun Ye, and Gen-Sheng Li. "The Global Shortest Path Visualization Approach with Obstructions." Journal of Robotics and Mechatronics 27, no. 5 (October 20, 2015): 579–85. http://dx.doi.org/10.20965/jrm.2015.p0579.

Full text
Abstract:
<div class=""abs_img""> <img src=""[disp_template_path]/JRM/abst-image/00270005/15.jpg"" width=""200"" />Shortest path experiment device</div> The avoidance obstacle path planning problem is stated in an obstacle environment. The minimum Steiner tree theory is the basis of the global shortest path. It is one of the classic NP-hard problem in nonlinear combinatorial optimization. A visualization experiment approach has been used to find Steiner point and system’s shortest path is called Steiner minimum tree. However, obstacles must be considered in some problems. An Obstacle Avoiding Steiner Minimal Tree (OASMT) connects some points and avoids running through any obstacle when constructing a tree with a minimal total length. We used a geometry experiment approach (GEA) to solve OASMT by using the visualization experiment device discussed below. A GEA for some systems with obstacles is used to receive approximate optimizing results. We proved the validity of the GEA for the OASMT by solving problems in which the global shortest path is obtained successfully by using the GEA. </span>
APA, Harvard, Vancouver, ISO, and other styles
31

Kortsarz, Guy, and Zeev Nutov. "The minimum degree Group Steiner problem." Discrete Applied Mathematics 309 (March 2022): 229–39. http://dx.doi.org/10.1016/j.dam.2021.12.003.

Full text
APA, Harvard, Vancouver, ISO, and other styles
32

Vedunova, M., A. Ignatova, and S. Titov. "The problem of blocking Steiner triples." Journal of the Ural Federal District Information security 19, no. 1 (2019): 23–30. http://dx.doi.org/10.14529/secur190104.

Full text
APA, Harvard, Vancouver, ISO, and other styles
33

Roanes-Macías, Eugenio, and Eugenio Roanes-Lozano. "3D extension of Steiner chains problem." Mathematical and Computer Modelling 45, no. 1-2 (January 2007): 137–48. http://dx.doi.org/10.1016/j.mcm.2006.04.012.

Full text
APA, Harvard, Vancouver, ISO, and other styles
34

Winter, Pawel. "Generalized steiner problem in outerplanar networks." BIT 25, no. 3 (September 1985): 485–96. http://dx.doi.org/10.1007/bf01935369.

Full text
APA, Harvard, Vancouver, ISO, and other styles
35

Duin, Cees, and Ton Volgenant. "The multi-weighted Steiner tree problem." Annals of Operations Research 33, no. 6 (June 1991): 451–69. http://dx.doi.org/10.1007/bf02071982.

Full text
APA, Harvard, Vancouver, ISO, and other styles
36

Lin, Guohui, and Guoliang Xue. "On the terminal Steiner tree problem." Information Processing Letters 84, no. 2 (October 2002): 103–7. http://dx.doi.org/10.1016/s0020-0190(02)00227-2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
37

Khuller, Samir, and An Zhu. "The General Steiner Tree-Star problem." Information Processing Letters 84, no. 4 (November 2002): 215–20. http://dx.doi.org/10.1016/s0020-0190(02)00271-5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
38

Xin-yao, Jiang. "The Steiner problem on a surface." Applied Mathematics and Mechanics 8, no. 10 (October 1987): 969–74. http://dx.doi.org/10.1007/bf02454259.

Full text
APA, Harvard, Vancouver, ISO, and other styles
39

Wu, Bang Ye, and Chen-Wan Lin. "On the clustered Steiner tree problem." Journal of Combinatorial Optimization 30, no. 2 (July 15, 2014): 370–86. http://dx.doi.org/10.1007/s10878-014-9772-7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
40

Segev, Arie. "The node-weighted steiner tree problem." Networks 17, no. 1 (1987): 1–17. http://dx.doi.org/10.1002/net.3230170102.

Full text
APA, Harvard, Vancouver, ISO, and other styles
41

Winter, Pawel. "Steiner problem in networks: A survey." Networks 17, no. 2 (1987): 129–67. http://dx.doi.org/10.1002/net.3230170203.

Full text
APA, Harvard, Vancouver, ISO, and other styles
42

Scott Provan, J. "Convexity and the Steiner tree problem." Networks 18, no. 1 (1988): 55–72. http://dx.doi.org/10.1002/net.3230180108.

Full text
APA, Harvard, Vancouver, ISO, and other styles
43

Miller, Zevi, and Manley Perkel. "The steiner problem in the hypercube." Networks 22, no. 1 (January 1992): 1–19. http://dx.doi.org/10.1002/net.3230220102.

Full text
APA, Harvard, Vancouver, ISO, and other styles
44

Lai, Katherine, Carla Gomes, Michael Schwartz, Kevin McKelvey, David Calkin, and Claire Montgomery. "The Steiner Multigraph Problem: Wildlife Corridor Design for Multiple Species." Proceedings of the AAAI Conference on Artificial Intelligence 25, no. 1 (August 4, 2011): 1357–64. http://dx.doi.org/10.1609/aaai.v25i1.7809.

Full text
Abstract:
The conservation of wildlife corridors between existing habitat preserves is important for combating the effects of habitat loss and fragmentation facing species of concern. We introduce the Steiner Multigraph Problem to model the problem of minimum-cost wildlife corridor design for multiple species with different landscape requirements. This problem can also model other analogous settings in wireless and social networks. As a generalization of Steiner forest, the goal is to find a minimum-cost subgraph that connects multiple sets of terminals. In contrast to Steiner forest, each set of terminals can only be connected via a subset of the nodes. Generalizing Steiner forest in this way makes the problem NP-hard even when restricted to two pairs of terminals. However, we show that if the node subsets have a nested structure, the problem admits a fixed-parameter tractable algorithm in the number of terminals. We successfully test exact and heuristic solution approaches on a wildlife corridor instance for wolverines and lynx in western Montana, showing that though the problem is computationally hard, heuristics perform well, and provably optimal solutions can still be obtained.
APA, Harvard, Vancouver, ISO, and other styles
45

DING, WEI, GUOHUI LIN, and GUOLIANG XUE. "DIAMETER-CONSTRAINED STEINER TREES." Discrete Mathematics, Algorithms and Applications 03, no. 04 (December 2011): 491–502. http://dx.doi.org/10.1142/s179383091100136x.

Full text
Abstract:
Given an edge-weighted undirected graph G = (V, E, c, w), where each edge e ∈ E has a non-negative cost c(e) and a non-negative weight w(e), a set S ⊆ V of terminals and a positive constant D0, we seek a minimum cost Steiner tree in which all terminals appear as leaves and the tree diameter is bounded by D0. Here the tree diameter is the maximum weight of the paths connecting two different leaves in the tree. Such a problem is called the minimum cost diameter-constrained Steiner tree problem. The problem is NP-hard even when the topology of the Steiner tree is fixed. In present paper we focus on this fixed topology restricted version and present a fully polynomial time approximation scheme for computing a minimum cost diameter-constrained Steiner tree.
APA, Harvard, Vancouver, ISO, and other styles
46

Bereta, Michał. "Monte Carlo Tree Search Algorithm for the Euclidean Steiner Tree Problem." Journal of Telecommunications and Information Technology 4 (December 20, 2017): 71–81. http://dx.doi.org/10.26636/jtit.2017.122017.

Full text
Abstract:
This study is concerned with a novel Monte Carlo Tree Search algorithm for the problem of minimal Euclidean Steiner tree on a plane. Given p p p points (terminals) on a plane, the goal is to find a connection between all the points, so that the total sum of the lengths of edges is as low as possible, while an addition of extra points (Steiner points) is allowed. Finding the minimum Steiner tree is known to be np-hard. While exact algorithms exist for this problem in 2D, their efficiency decreases when the number of terminals grows. A novel algorithm based on Upper Confidence Bound for Trees is proposed. It is adapted to the specific characteristics of Steiner trees. A simple heuristic for fast generation of feasible solutions based on Fermat points is proposed together with a correction procedure. By combing Monte Carlo Tree Search and the proposed heuristics, the proposed algorithm is shown to work better than both the greedy heuristic and pure Monte Carlo simulations. Results of numerical experiments for randomly generated and benchmark library problems (from OR-Lib) are presented and discussed.
APA, Harvard, Vancouver, ISO, and other styles
47

Bonafini, M. "Convex relaxation and variational approximation of the Steiner problem: theory and numerics." Geometric Flows 3, no. 1 (March 1, 2018): 19–27. http://dx.doi.org/10.1515/geofl-2018-0003.

Full text
Abstract:
Abstract We survey some recent results on convex relaxations and a variational approximation for the classical Euclidean Steiner tree problem and we see how these new perspectives can lead to effective numerical schemes for the identification of Steiner minimal trees.
APA, Harvard, Vancouver, ISO, and other styles
48

Li, Xiao Yi, Zhao Di Xu, and Wan Xi Chou. "Methods of Constructing and Enumerating the Steiner Triple System with Order 31." Applied Mechanics and Materials 513-517 (February 2014): 3061–64. http://dx.doi.org/10.4028/www.scientific.net/amm.513-517.3061.

Full text
Abstract:
This paper describes the basic concept of constructing Steiner triple system of order and gives the definition edge matrix of a complete graph. It proposes a method of constructing Steiner triple system of order. The entire procedure of constructing Steiner triple system of order .It discusses the enumeration problem of Steiner triple system.
APA, Harvard, Vancouver, ISO, and other styles
49

WENG, J. F., D. A. THOMAS, and I. MAREELS. "IDENTIFYING STEINER MINIMAL TREES ON FOUR POINTS IN SPACE." Discrete Mathematics, Algorithms and Applications 01, no. 03 (September 2009): 401–11. http://dx.doi.org/10.1142/s1793830909000324.

Full text
Abstract:
A Steiner minimal tree is a network with minimum length spanning a given set of points in space. There are several criteria for identifying the Steiner minimal tree on four points in the Euclidean plane. However, it has been proved that the length of the Steiner minimal tree on four points cannot be computed using radicals if the four points lie in Euclidean space. This unsolvability implies that it is unlikely that similar necessary and sufficient conditions exist in the spatial case. Hence, a problem arises: Is it possible to generalize the known planar criteria to space in the sense that they are sufficient to identify Steiner minimal trees on four points in space? This problem is investigated and some sufficient conditions are proved in this paper. These sufficient conditions can help us to solve the general Steiner tree problem on n(> 4) points in Euclidean space.
APA, Harvard, Vancouver, ISO, and other styles
50

Chopra, Sunil, and Kalyan T. Talluri. "Minimum-Cost Node-Disjoint Steiner Trees in Series-Parallel Networks." VLSI Design 4, no. 1 (January 1, 1996): 53–57. http://dx.doi.org/10.1155/1996/43738.

Full text
Abstract:
The routing problem in VLSI-layout can be modeled as a problem of packing node-disjoint Steiner trees in a graph. The problem is as follows: Given an undirected network G = (V, E) and a net list Ψ {Ni, i = 1,..., r} , a family ΓG={TNi = (VNi , ENi), i = 1,..., r} is a node-disjoint family of Steiner trees spanning Ψ if TNi , is a Steiner tree spanning Ni for i = 1, ..., r and VNi ∩ VNj = for i ≠ j. The edge-disjoint version of this problem is known to be NP-hard for t. series-parallel graphs (see Rlchey and Parker [5]). In this paper we give a O(n5) algorithm for finding a minimum-cost node-disjoint family of Steiner trees in series-parallel networks. Our algorithm can be extended to k-trees and is polynomial for fixed k.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the bibliographies on the topic 'Steiner problem' for other source types:
Dissertations / Theses Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography