Sage Journals: Discover world-class research

Abstract

The underlying models of many practical problems in various engineering fields are equivalent to the Steiner tree problem in graphs, which is a typical NP-hard combinatorial optimization problem. Thus, developing a fast and effective heuristic for the Steiner tree problem in graphs is of universal significance. By analyzing the advantages and disadvantages of the fast classic heuristics, we find that the shortest paths and Steiner points play important roles in solving the Steiner tree problem in graphs. Based on the analyses, we propose a Steiner point candidate-based heuristic algorithm framework (SPCF) for solving the Steiner tree problem in graphs. SPCF consists of four stages: marking ${SPC}_{I}$ points, constructing the Steiner tree, eliminating the detour paths, and ${SPC}_{II}$ -based refining stage. For each procedure of SPCF, we present several alternative strategies to make the trade-off between the effectiveness and efficiency of the algorithm. By finding the shortest path clusters between vertex sets, several methods are proposed to mark the first type of Steiner point candidates ${SPC}_{I}$ . The solution qualities of the classic heuristics are effectively improved by looking ${SPC}_{I}$ points as terminals. By constructing a Voronoi diagram, a series of methods are suggested to mark the second type of Steiner point candidates ${SPC}_{II}$ . The feasible solution quality is efficiently improved by employing the ${SPC}_{II}$ points as the insertable key-vertices in key-vertex insertion local search method. Numerical experiments show that the proposed strategies are all effective for improving the solution quality. Compared with other effective algorithms, the proposed algorithms can achieve better solution quality and speed performance.

Keywords

NP-hard Steiner tree problem in graphs Steiner points Voronoi diagram

Introduction

The Steiner tree problem in graphs (GSTP) is a classic combinatorial optimization problem and is the underlying model for many practical problems in various engineering fields, such as the multiple destination routing of communication networks,^1–3 the physical design of very large scale integrated circuits (VLSI),^4,5 the transportation systems,^6–8 and the pipe systems.^9,10

The GSTP has been proved to be NP-hard.¹¹ Since the 1960s, researchers have focused on solving this problem. Exact algorithms,^12,13 approximation algorithms,^14,15 heuristics,^16–18 local search algorithms,^19–22 computational intelligence algorithms,^1–3 and reduction techniques^23–25 are suggested. Although the exact algorithms can provide an optimal solution to a GSTP, they require exponential running time. Contrary, the approximation algorithms are polynomial-time algorithms, and the approximation ratio of the GSTP has been improved from 2 to 1.39.¹⁵ The classic heuristics (shortest path heuristic (SPH)¹⁶ and distance network heuristic (DNH)¹⁷), which are fast and simple, are widely employed in engineering applications^4,5,26 and are used to construct initial feasible solutions for iterative methods, such as local search and computational intelligence algorithms. However, the solution quality of classic heuristics has significant room for improvement.^2,22 Key node-based minimum cost path heuristic (KBMPH)²⁷ is a variant of SPH which can obtain better solutions than SPH. The average distance heuristic (ADH)^18,28 is a well-known heuristic that can come up with much better solutions than those obtained by the classic algorithms with longer running time. Local search algorithms start from an initial feasible solution and perform a local search strategy iteratively until they obtain the local optimum solutions. Computational intelligence algorithms contain a cooperative multi-start local search strategy and a stochastic search strategy to improve the initial feasible solution quality.¹ Due to the unpredictable number of iterations, the local search and computational intelligence algorithms require significant running time. In addition, the running time and solution quality of these iterative methods are sensitive to the choice of initial feasible solution. The reduction technique is a preprocessor procedure for the GSTP that reduces the running time of the construction algorithm (CA) by reducing the size of the input instance equivalently. It is not discussed in this paper.

Since researchers pay more attention to reduce the approximation ratio rather than the running time, the high computational complexity of the approximation algorithms interferes with solving practical instances. In the engineering fields, there are large size GSTP problems, and the CA requests high real-time performance and excellent solution quality. A fast and effective heuristic for the GSTP is of universal significance for a wide range of applications. Here, we focus on improving the solution quality of the classic algorithms with reasonable running times. By analyzing the advantages and disadvantages of the fast classic heuristics, we find that the shortest paths and Steiner points play important roles in solving the GSTP. Based on the analyses, we present a Steiner point candidate-based heuristic algorithm framework (SPCF) for solving a GSTP. By finding the shortest path clusters between vertex sets, a series of methods are proposed to mark the first type of Steiner point candidates ${SPC}_{I}$ . The solution qualities of the classic heuristics are effectively improved by looking ${SPC}_{I}$ points as terminals. By constructing a Voronoi diagram, a series of methods are suggested to mark the second type of Steiner point candidates ${SPC}_{II}$ . The feasible solution quality is efficiently improved by employing the ${SPC}_{II}$ points as the insertable key-vertices in key-vertex insertion local search method. SPCF consists of four stages: marking ${SPC}_{I}$ points, constructing the Steiner tree, eliminating the detour paths, and ${SPC}_{II}$ -based refining stage. For each procedure of SPCF, we develop several alternative strategies to make the trade-off between the effectiveness and efficiency of the algorithm.

To verify the rationality and validity of the algorithm framework, numerous experiments are conducted on the well-known SteinLib benchmarks.²⁹ The effectiveness and efficiency of the proposed strategies of the framework are illustrated. Experimental results show that the proposed algorithm greatly improves solution quality of the two classic heuristics.^16,17 Compared with the ADH,²⁸ KBMPH,²⁷ the loss-contracting algorithm (LCA),¹⁴ and LP-based iterative randomized rounding (LPIRR),¹⁵ the proposed algorithm achieves better solution quality within shorter running times. LCA and LPIRR are the most recent approximation algorithms with approximation ratios of 1.55 and 1.39, respectively. The Dreyfus–Wagner (DW) algorithm¹² is a practical exact algorithm that applies a dynamic programming approach. If the number of the terminals is a constant, DW algorithm can obtain an optimal Steiner tree in polynomial time. In our testing environment, the DW algorithm is unable to solve instances in which the number of terminals is greater than 20.

The remainder of this paper is organized as follows. In section Preliminaries, we present basic descriptions of the GSTP and Voronoi diagram, review two classic heuristics,^16,17 and discuss the importance of the shortest path and the Steiner point in the GSTP. The SPCF framework and related strategies are presented in section Steiner Point Candidate Based Heuristic Algorithms. Experimental comparisons are described in section Computational Experiments, and conclusions and suggestions for future work are presented in section Conclusion.

Preliminaries

Steiner tree problem in graphs

Definition 1

In the GSTP, given a weighted undirected connected graph $G = (V, E, ω)$ and a subset of vertices $T \subseteq V$ , $V = {v_{1}, v_{2}, \dots, v_{n}}$ is the set of vertices in G, and n denotes the number of the vertices. $E = {e_{1}, e_{2}, \dots, e_{m}}$ represents the set of edges in G, m is the number of edges, and $ω : E \to R^{+}$ denotes the weight function that maps each edge onto the corresponding weight in the graph. $T = {t_{1}, t_{2}, \dots, t_{l}}$ is a set of special vertices, which are referred to as terminals, and l denotes the number of terminals. The goal of the problem is to connect all terminals with a tree subgraph $G_{s} = (V_{s}, E_{s}, ω), T \subseteq V_{s} \subseteq V, E_{s} \subseteq E$ of G, such that the total weight $W_{s} = \sum_{e \in E_{s}} ω (e)$ of the tree is the minimum.

In a Steiner tree, let “node” denote a nonterminal vertex, let “Steiner point” denote a node with a degree of at least three. Together, the Steiner points and terminals are referred to as a “key-vertex.” Let “key-path” be a path, of which the ends are key-vertices and each internal vertex is a node with a degree of two.

Voronoi diagram and construction

The Voronoi diagram method is a very effective tool for solving the GSTP.^22,30,31

Given a weighted undirected connected graph $G' = (V', E', ω')$ , let $Path (u, v)$ denote the shortest path between vertices $u and v$ with respect to the weight function $ω'$ , and $D (u, v)$ denote the weight of $Path (u, v)$ . Let $D (u, A) = \inf {D (u, v) | v \in A}$ denote the distance between the vertex u and the vertex set A.

Definition 2

Given a weighted undirected connected graph $G' = (V', E', ω')$ and a set of seed vertices $S \subseteq V'$ , for each seed $S \in S$ , there is a corresponding region (i.e. a Voronoi cell denoted as $S . cell$ ) consisting of all vertices in $V'$ closer to S than to other seeds, $S . cell = {u \in V' | D (u, S) \leq D (u, S^{'}) for all S' \in S and$ $S' \neq S}$ . The Voronoi diagram is a partition of $V'$ . In other words, the Voronoi cells are disjointed.

In this paper, a seed S can be a set of vertices, and then $S$ denotes the set of seeds, where $\cup S \subseteq V$ .

Let $u . cell$ denote the Voronoi cell which contains u. Let $u . seed$ denote the seed of $u . cell$ , and let $u . dist = D (u, u . seed)$ .

Between two adjacent Voronoi cells $S_{i} . cell and S_{j} . cell$ , let bridge $b (u, v)$ denote an edge $e (u, v)$ that connects $S_{i} . cell and S_{j} . cell$ , where $u \in S_{i}$ and $v \in S_{j}$ . Let $b (u, v) . span = u . dist + v . dist + ω' (e (u, v))$ be the span of the bridge $b (u, v)$ . Let the main bridge between $S_{i} . cell and S_{j} . cell$ denote a bridge with the shortest span among all bridges between $S_{i} . cell and S_{j} . cell$ . $MBs (S_{i}, S_{j})$ denotes the main bridge set that consists of all main bridges between $S_{i} . cell and S_{j} . cell$ .

If a vertex and its neighbors belong to more than three Voronoi cells, this vertex is denoted as an adjacent vertex of the Voronoi diagram.

Property 1

The Voronoi diagram of a weighted undirected connected graph $G' = (V', E', ω')$ can be constructed in $O (| E' | \log | V' |)$ time.^22,30

Classic heuristic algorithms

DNH¹⁷ and SPH,¹⁶ the classic heuristics discussed in this paper, are two well-known heuristics for the GSTP. Although they are both 2-approximation algorithms, they can obtain a good solution for most instances in practice and require short running time. Researchers usually employ them as independent construction methods for various practical GSTP problems.^{1–5,19–22,26,32–34}

DNH

The original DNH, which reduces the GSTP to a minimum-weight terminal spanning tree, has a worst-case time complexity of $O ({mn}^{2})$ with an approximation ratio of $2 (1 - 1 / α)$ ,¹⁷ where α is the number of the leaves in the optimal tree. The worst-case time complexity is improved to $O (m \log n)$ with binary heaps or $O (m + n \log n)$ with Fibonacci heaps.^30,35 The improved version of the DNH algorithm³⁰ consists of two steps.

Divide the graph G into l Voronoi cells by considering each terminal as a seed.

The span of the main bridge of each pair of adjacent Voronoi cells is considered the weight of the virtual edge between the responding two seeds (terminals). Then, connect the terminals with the virtual edges using a minimum spanning tree algorithm.

SPH

The original SPH can be considered a modified version of Prim’s algorithm for the GSTP, which requires a worst case time of $O (lm \log n)$ and has an approximation ratio of $2 (1 - 1 / l)$ .^16,31 SPH is an iterative process.

Initialize the partial solution $G_{p} = (V_{p}, E_{p})$ with an arbitrary terminal $t \in T$ , i.e. $E_{p} = Φ, V_{p} = {t}$ .

By implementing Dijkstra’s algorithm, find the closest terminal $u'$ to G_p, i.e. $u' \in T \ (V_{p} \cap T), D (u', V_{p}) = \inf (D (u, V_{p}) | u \in T \ (V_{p} \cap T))$ , and update G_p by adding $Path (u', x')$ to G_p, where $x' \in V_{p}$ and $D (u', x') = D (u', V_{p})$ .

Repeat step (2) until $T \subseteq V_{p}$ .

Similar to Prim’s algorithm, the solution quality of SPH is sensitive to the choice of the starting terminal.

Although DNH has less worst-case complexity, SPH, which is approximately as fast as DNH in practice, can achieve a better implementation.³¹

Shortest paths and Steiner point candidates

Finding the shortest path is a basic greedy strategy employed by the classic heuristics to construct the Steiner tree.

Property 2

For any optimal solution of the GSTP, any key-path is a shortest path between a pair of key-vertices.

Proof

By contradiction, the property is obviously true. ▪

Definition 3

In a GSTP, A Steiner point candidate is a nonterminal vertex, which is expected to be passed by the constructed Steiner tree.

A good Steiner point candidate can induce the constructed Steiner tree to pass through or close to a Steiner point of some optimal solution, which can improve the solution quality. Different strategies can mark different Steiner point candidates.

Property 3

Given a feasible solution $G_{s} = (V_{s}, E_{s}, ω)$ for a GSTP, if the key-vertices of G_s are considered the terminals, the corresponding minimum-weight terminal spanning tree $G'_{s}$ costs no more than G_s. In addition, if G_s is optimal, $G'_{s}$ is also optimal.^22,33,36,37

Thus, if we set all the key-vertices of some optimal solution as the Steiner point candidates, we can construct an optimal solution by using DNH to connect the terminals and Steiner point candidates with the shortest paths. Unfortunately, determining which nonterminal vertex is a Steiner point is difficult and is equivalent to solving the GSTP.²⁸ Thus, determining how to locate the Steiner point candidates is the key of solving a GSTP.

A general algorithm framework based on finding the Steiner point candidates is proposed in Rayward-Smith and Clare²⁸ (denoted with RS framework). First, the Steiner points of a feasible solution obtained by the heuristics for the GSTP are marked as the Steiner point candidates. Then, the final solution is constructed by employing a minimum-weight terminal spanning tree algorithm to connect the terminals and the Steiner point candidates. This framework improves the quality of the solution obtained by the corresponding heuristic. Our algorithm is in line with this framework, and we propose two methods to locate two types of Steiner point candidates ( ${SPC}_{I}$ and ${SPC}_{II}$ ).

Steiner point candidate-based heuristic algorithms

Our algorithms consist of four stages: marking the Steiner point candidates ${SPC}_{I}$ , constructing the Steiner tree, eliminating the detour paths and ${SPC}_{II}$ -based refining stage.

Marking the Steiner point candidates ${SPC}_{I}$

We extend the shortest paths between two vertices to the shortest path clusters between two vertex sets.

Definition 4

$A, B$ are two nonempty disjointed vertices vertex. Let $D (A, B) = \inf {D (u, v) | u \in A, v \in B}$ denote the distance between the two vertex sets A and B. If $D (a, b) = D (A, B), a \in A, b \in B$ , the corresponding shortest $Path (a, b)$ is referred to as the shortest path between A and B, and $a, b$ are referred to as the connected points. The path set that consists of all shortest paths between A and B is referred to as the shortest path cluster between A and B (denoted as $SPS (A, B)$ ).

Inspired by the classic heuristics and RS framework, the Steiner point candidates, which can reduce the weight of the constructed Steiner tree, are generally located along some shortest paths. In each step of the classic heuristics, the choice from the available shortest paths could generate different overlapping edges, which can reduce the weight of the Steiner tree. We cannot determine which shortest path is the best choice among all of the available shortest paths. Thus, we employ shortest paths clusters to connect terminals rather than the shortest paths. The connected points which are nonterminals are marked as a Steiner point candidate ${SPC}_{I}$ . This heuristic strategy is referred to as the shortest path cluster heuristic (SPSH). The SPSH algorithm is an iterative procedure that consists of four phases: the initial phase, the spreading phase, the tracing-back phase, and the updating phase. The last three phases are repeated until all terminals are connected by the shortest path clusters. The input of the SPSH algorithm contains the information of the GSTP, and the output is a set ${SPC}_{I}$ points.

Depending on the different connecting strategies, we develop three types of SPSH algorithm: single source shortest path cluster heuristic (SS_SPSH), multi-source shortest path cluster heuristic (MS_SPSH), and multi-source parallel shortest path cluster heuristic (MSP_SPSH).

Single source shortest path cluster heuristic

In each iteration of the SS_SPSH, we connect a closest terminal to the connected vertex set with a shortest path cluster until the connected vertex set contains all of the terminals.

The detailed iterative procedure is as follows.

In the initial phase, a connected vertex set is initialized with an arbitrary terminal and denoted as $CV$ ;

In the spreading phase, we find a closest terminal $u \in T \ (CV \cap T)$

to $CV$ with Dijkstra’s algorithm where

(4) $D (u, CV) = \inf {D (v, CV) | v \in T \ (CV \cap T)}$ . Dijkstra’s algorithm begins by considering $CV$ as the source and is suspended when closest terminal u is traversed.

In the tracing-back phase, we obtain the shortest path cluster $SPS (CV, {u})$ by implementing a recursive procedure. We get the precursors of the current vertex (initialized with u) on $SPS (CV, {u})$ according to the weight of the edges and the distance between each vertex and the source. Then, each precursor is considered the current vertex to determine the next precursors. If a precursor belongs to $CV$ , it is a connected point and the recursive branch is terminated.

In the updating phase, we update $CV$ by inserting all vertices on $SPS (CV, {u})$ .

With the exception of the first iteration, Dijkstra’s algorithm does not need to start from scratch. We only need to continue Dijkstra’s algorithm by considering newly inserted vertices of $CV$ as sources.

Property 4

The computation complexity of the SS_SPSH is $O (lm lg n)$ .

Proof

The SS_SPSH consists of $(l - 1)$ iterations, and each iteration performs once Dijkstra’s algorithm, which takes $O (m lg n)$ time in the worst case.³⁸ As shown in line 32 of Figure 1, the distance of the tracing back node is set to zero, and each node is visited at most once. The tracing-back and updating phases require at most $O (n)$ time. Thus, the computation complexity of the SS_SPSH is $O (lm lg n)$ . ▪

Figure 1.

SS_SPSH pseudocode.

The detailed pseudo code of the SS_SPSH is shown in Figure 1.

Multi-source shortest path cluster heuristic

In each iteration of the MS_SPSH, we connect the closest two connected vertex sets with a shortest path cluster until only one connected vertex set remained.

The detailed iterative procedure is as follows:

In the initial phase, each terminal is used to initialize a connected vertex set, and l connected vertex sets ${CV}_{1} \dots {CV}_{l}$ are created.

In the spreading phase, we find a pair of closest connected vertex sets ${CV}_{i} and {CV}_{j}$ with the Voronoi diagram method. The Voronoi diagram method begins by considering each connected vertex set as a seed and is suspended when all main bridges $MBs ({CV}_{i}, {CV}_{j})$ are found.

In the tracing-back phase, we collect the shortest path cluster $SPS ({CV}_{i}, {CV}_{j})$ . This is a similar recursive procedure to the tracing-back phase of SS_SPSH; however, each end of all main bridges between ${CV}_{i} and {CV}_{j}$ are considered the current vertices.

In the updating phase, we update the connected vertex sets by creating a new connected vertex set ${CV}_{n}$ to replace ${CV}_{i} and {CV}_{j}$ , where ${CV}_{n} = SPS ({CV}_{i}, {CV}_{j}) \cup {CV}_{i} \cup {CV}_{j}$ .

With the exception of the first iteration, the Voronoi diagram method does not need to start from scratch. We only need to continue the Voronoi diagram method by considering ${CV}_{n}$ as a new seed.

Property 5

The computation complexity of the MS_SPSH is $O (lm lg n)$ .

Proof

The MS_SPSH consists of $(l - 1)$ iterations. Each iteration contains a Voronoi diagram procedure, which requires $O (m \log n)$ time in the worst case. The tracing-back and updating phases require at most $O (n)$ time. Thus, the computation complexity of MS_SPSH is $O (lm lg n)$ . ▪

Compared with SS_SPSH, MS_SPSH must maintain a minimum-priority queue to sort the bridges with the spans and expand the spreading range of the Dijkstra’s algorithm to find all main bridges between the closest two connected vertex sets in the spreading phase. The detailed pseudo code of the MS_SPSH is shown in Figures 2 and 3.

Figure 2.

MS_SPSH pseudocode.

Figure 3.

TraceBack2 pseudocode.

Multi-source parallel shortest path cluster heuristic

In each iteration of the MSP_SPSH, we connect several pairs of closest connected vertex sets with the shortest path clusters until only one connected vertex set remained.

The detailed iterative procedure is as follows.

The initial phase, tracing-back phase, and updating phase are all similar to MS_SPSH, with the exception that the Voronoi seeds are all unstamped in the initial and updating phases, and there are several shortest path clusters that must be handled in the tracing-back and updating phases.

In the spreading phase, we find several pairs of closest connected vertex sets with the Voronoi diagram method. The Voronoi diagram method begins by considering each connected vertex set as a seed. There is a sub iteration to find a pair of closest unstamped connected vertex sets that is similar to the spreading phase of MS_SPSH. Then, this pair of connected vertex sets is stamped. If a connected vertex set is stamped, the spreading procedure of the corresponding Voronoi cell is suspended and the associated bridges are discarded in this iteration. The Voronoi diagram method is suspended when all seeds are stamped.

With the exception of the first iteration, the Voronoi diagram method does not need to start from scratch; we only need to continue the Voronoi diagram method by considering the new connected vertex sets as new seeds.

Property 6

The computation complexity of the MSP_SPSH is $O (lm lg n)$ .

Proof

The MSP_SPSH consists of at most $(l - 1)$ iterations, and each iteration contains a Voronoi diagram procedure, which requires $O (m \log n)$ time in the worst case. Thus, the computation complexity of the MSP_SPSH is $O (lm \log n)$ . ▪

Compared with SS_SPSH and MS_SPSH, MSP_SPSH must take the bridges, which are not yet processed, along to the next iteration. The detailed pseudo code of the MSP_SPSH is shown in Figures 4 and 5.

Figure 4.

MSP_SPSH pseudocode.

Figure 5.

TraceBack3 pseudocode.

Construction algorithms

We consider the Steiner point candidates as the terminals and employ a classic heuristic to construct a feasible solution that can connect the Steiner point candidates and the terminals. Since the Steiner point candidates are fake terminals, some unnecessary paths may be generated. In these paths, the intermediate vertices are all nodes with a degree of two, and one of the ends is a nonterminal vertex with a degree of one. An additional pruning operation is employed to delete the unnecessary paths. Although DNH has less worst-case complexity, SPH, which is approximately as fast as DNH in practice, can achieve a better implementation.³¹ In this paper, the SPH is employed as the CA except where otherwise noted.

Eliminating the detour paths

A bad Steiner point candidate may result in the constructed Steiner tree containing some detour paths which are key-paths and not shortest paths, as shown in Figure 6(a) and (b).

Figure 6.

Example of eliminating the detour paths.

Two strategies for eliminating the detour paths are proposed and denoted as EDP_RS and EDP_KPE, respectively. EDP_RS, which is in line with RS framework,²⁸ marks the Steiner points of the presolution as the Steiner point candidate, as shown in Figure 6(b)–(d), and executes the CA repeatedly until the quality of the solution cannot be improved. Unfortunately, we cannot forecast the number of loops, which is small in the experiments. We set five as the bounding number of loops. Thus, the computation complexity of EDP_RS is $O (lm \log n)$ . EDP_KPE employs the key-path exchange method,²² as shown in Figure 6(b), (e) and (f). The key-path exchange replaces each key-path with a new key-path that does not cost more than the old one and requires $O (m \log n)$ time. Each implementation of the CA is followed by one of the detour path eliminating strategies, except where otherwise noted.

SPC_II-based refining strategies

SPSH and classic heuristics are all shortest path-based greedy methods which can used for marking the Steiner point candidates. For some specific GSTP instances, the shortest path-based methods cannot pass through some Steiner points of the optimal solutions of these instances. This type of Steiner points is referred to as hard-nodes, and this type of GSTP instances are referred to as hard GSTP instances. Classic heuristics generally generate poor quality solutions for hard GSTP instances. SPSH algorithms cannot mark the location of the hard-nodes. As shown in Definition 5, the complete-wheel graph is a classic type of hard GSTP instance.

Definition 5

A complete-wheel graph is a GSTP instance where G is a complete graph and $l = n - 1, (n > 3)$ . The only nonterminal vertex is referred to as the center vertex. An edge incident to two terminals is referred to as internal edge with weight $2 * β$ , and an edge incident to the center vertex is a wheel arm edge with weight $β + τ$ , where $β >> τ > 0$ .

An optimal solution of the complete-wheel graph consists of l wheel arm edges with weight $l * (β + τ)$ , while the feasible solutions constructed by classic heuristics consist of $l - 1$ internal edges with weight $2 * (l - 1) * β$ . As shown expression (1), the weight ratio of the feasible solution to the optimal solution is the approximation ratio of the classic heuristics. The complete-wheel graph is a hard GSTP instance, and the center vertex is a hard-node. As well as, SPSH algorithms cannot mark the center vertex of the complete-wheel graph as Steiner point candidate. A partial complete-wheel graph which contains at least $l - 1$ internal edges and all the arm edges remains a hard GSTP instance.

{lim}_{\frac{τ}{β} \to 0} 2 * (1 - \frac{1}{l} * \frac{β + τ * l}{β + τ}) = 2 (1 - \frac{1}{l})

(1)

As shown in Figure 7, there is a complete-wheel graph with $n = 6, β = 1, τ = 0.1$ .

Figure 7.

Illustration of a complete-wheel graph $n = 6, β = 1, τ = 0.1$ . An optimal solution with weight 5.5. A feasible solution constructed by classic heuristics with weight 8.

Property 7

If a GSTP instance contains some complete-wheel graphs or partial complete-wheel graphs, the center vertices are the adjacent vertices of the Voronoi diagram which is built by look the terminals as seeds.

Proof

Based on Definition 5, there are at least three neighbor vertices of each center vertex are terminals. Thus, the center vertices are the adjacent vertices of the Voronoi diagram which is built by look the terminals as seeds. ▪

Based on Property 7, three alternative strategies, which are used to refine the quality of the solutions obtained by the shortest path-based algorithms for hard GSTP instances, are proposed and denoted as IS-I, IS-II, and IS-III.

First, a Voronoi diagram is constructed by considering each terminal as a seed in G.

In IS-I, all of the adjacent vertices of the Voronoi diagram are looked as ${SPC}_{II}$ . For each ${SPC}_{II}$ , we perform a greedy procedure. A new solution is constructed by connecting the key-vertices of the presolution and the selected ${SPC}_{II}$ with a CA. If the new solution costs less than the presolution, we replace the presolution with the new one.

Property 8

The computation complexity of the IS-I is $O (nlm lg n)$ .

Proof

By Property 1, the construction of the Voronoi diagram takes $O (m lg n)$ time in the worst case. There are at most $O (n)$ adjacent vertices of the Voronoi diagram. Moreover, the IS-I requires execution of the CA at most $O (n)$ times. SPH algorithm which requires a worst-case time of $O (lm \log n)$ .^16,31 Thus, if SPH is employed as the CA, the computation complexity of the IS-I is $O (nlm lg n)$ . ▪

IS-I is effective with longer running time. IS-II reduces the number of ${SPC}_{II}$ for increasing efficiency and performs the same greedy procedure as IS-I. A new Steiner tree (denoted as $T_{new}$ ) is constructed by connecting all of the adjacent vertices of the Voronoi diagram and terminals with a CA. The Steiner points of $T_{new}$ are marked as ${SPC}_{II}$ for IS-II.

Property 9

The computation complexity of the IS-II is $O (l^{2} m lg n)$ .

Proof

There are at most $O (l)$ Steiner points of $T_{new}$ .³⁹ Thus, the IS-II requires execution of the CA at most $O (l)$ times. Thus, the computation complexity of the IS-II is $O (l^{2} m lg n)$ . ▪

IS-III adopts a Steiner tree merging method rather than iteratively executing the CA to further increase efficiency. A graph (denoted as NG), which is composed of the union of the edges of the presolution and the $T_{new}$ , is built. IS-III constructs the final solution by connecting the nonterminal vertices with a degree of at least three of the NG and terminals with a CA. IS-III executes the CA twice. Thus, we can get Property 10.

Property 10

The computation complexity of the IS-III is $O (lm lg n)$ .

Generally, the CA employed by the IS strategies does not contain an EDP strategy to save running time. Otherwise, the IS which contains an EDP strategy is denoted as IS^#, which requires more time and obtains a better solution.

Main framework of the SPCF

Here, a three-stage main framework of SPCF is presented for the GSTP. The pseudo code is shown in Figure 8. The computation complexities of four types of strategies outlined in the previous section are summarized in Table 1. Based on the SPCF, a variety of algorithms can be constituted using the proposed strategies to find an appropriate tradeoff between solution quality and running time. As shown in Table 2, we list nine groups of SPCF algorithms. Each group of algorithms consists of three algorithms with different SPSH strategies. The first six groups focus on improving the solution quality by inserting or exchanging the strategies, and the last three groups focus on saving running time by exchanging the strategies.

Figure 8.

SPCF pseudocode.

Table 1.

Computational complexities of the mentioned strategies.

Types	Strategies	complexity
SPSH	MSP_SPSH	$O (lm \log n)$
	MS_SPSH	$O (lm \log n)$
	SS_SPSH	$O (lm \log n)$
CAs	DNH	$O (m \log n)$
CAs	SPH	$O (lm \log n)$
EDP	EDP_RS	$O (lm \log n)$
EDP	EDP_KPE	$O (m \log n)$
IS	IS-I^#	$O (nlm \log n)$
	IS-I	$O (nlm \log n)$
	IS-II	$O (l^{2} m \log n)$
	IS-III	$O (lm \log n)$

IS-I^# represents that the construction algorithm of refining strategy IS-I contains the corresponding EDP strategy.

Table 2.

Computational complexities of the nine groups of SPCF algorithms.

Steiner point candidate-based heuristic algorithms
Algorithms	Constituents	Complexity
*_SPCF-I	*_SPSH+DNH	$O (lm \log n)$
*_SPCF-II	*_SPSH+SPH	$O (lm \log n)$
*_SPCF-III	*_SPSH+SPH+EDP_RS	$O (lm \log n)$
*_SPCF-IV	*_SPSH+SPH+EDP_KPE	$O (lm \log n)$
*_SPCF-V	*_SPSH+SPH+EDP_KPE+IS-I^#	$O (nlm \log n)$
*_SPCF-VI	*_SPSH+SPH+EDP_RS+IS-I^#	$O (nlm \log n)$
*_SPCF-VII	*_SPSH+SPH+EDP_RS+IS-I	$O (nlm \log n)$
*_SPCF-VIII	*_SPSH+SPH+EDP_RS+IS-II	$O (l^{2} m \log n)$
*_SPCF-IX	*_SPSH+SPH+EDP_RS+IS-III	$O (lm \log n)$

‘*’ represents “MSP,” “MS,” and “SS” shortest path cluster heuristics. IS-I^# represents that the construction algorithm of refining strategy IS-I contains the corresponding EDP strategy.

Computational experiments

The widely used SteinLib benchmark²⁹ is adopted in the experiments. The optimal solutions or the best near-optimal solutions of the instances that have been reported in the literature are published in SteinLib. We assemble a set of instances (denoted as TestCase) with 389 instances from SteinLib to compare the algorithms in appropriate running time. In the TestCase, the number of terminals is not more than 20, and the number of vertices is not more than 1000. Basic information for TestCase is presented in Table 3, and the instances of TestCase are listed in Appendix 1.

Table 3.

Basic information for SteinLib TestCase instances.

	Size	Description	n	m	l
TestCase	389	$n \leq 1000 and l \leq 20$	6–1000	9–204480	3–20

We conducted two tests to examine the performance of SPCF algorithms for solving the GSTP. First, we tested the nine groups of SPCF algorithms to evaluate the effectiveness of the proposed strategies. Second, we compare the most effective SPCF algorithm with five typical algorithms.^{12,14,15,27,28}

The percentage relative error with respect to the best-known solutions is commonly used to evaluate the quality of solutions found by a specific algorithm. As shown in expression (2), $G_{opt}$ denotes the best solution reported in the literature thus far, G_s denotes the solution found by a specific algorithm, and $Ω ()$ denotes the weight function. For each instance, the algorithm is executed 20 times, and the arithmetic mean (denoted as $PR_ERR_avg$ ) and the minimum (denoted as $PR_ERR_best$ ) of the percentage relative errors of the 20 solutions are taken as the final values of the instance. For the set of instances TestCase, let $AVG_PR_ERR$ denote the aggregate average percentage relative error that is shown in expression (3), and let $BEST_PR_ERR$ denote the aggregate best percentage relative error that is shown in expression (4).

As suggested by Aragão and Werneck,³¹ to achieve a language- and machine-independent aggregate time, Prim’s algorithm implemented with a binary heap is selected as the baseline method to measure the relative running time of each instance. For an instance, the relative running time is shown in expression (5), where ${time}_{s}$ denotes the running time of a specific algorithm, and ${time}_{prim}$ denotes the running time of Prim’s algorithm. As shown in expression (6), the aggregate relative running time of a set of instances TestCase is the geometric mean of the relative running times of the instances.

PR_ERR = \frac{Ω (G_{s}) - Ω (G_{opt})}{Ω (G_{opt})} \times 100 %

(2)

AVG_PR_ERR = \frac{1}{389} \times \sum_{x \in TestCase} PR_ERR_{avg}_{x}

(3)

BEST_PR_ERR = \frac{1}{389} \times \sum_{x \in TestCase} PR_ERR_{best}_{x}

(4)

RT = \frac{{time}_{s}}{{time}_{prim}}

(5)

GEO_RT = \sqrt[389]{\underset{x \in TestCase}{Π} {RT}_{x}}

(6)

Our SPCF algorithms and the compared algorithms are implemented in C++ and compiled using GCC 4.4.7. The Floyd–Warshall algorithm is used to build the metric closure of G for KBMPH, ADH, and DW. The DW algorithm is employed to construct the k-full-component for LCA and LPIRR. IBM CPLEX is adopted to solve the LP problem in LPIRR. Although a larger parameter k of LCA and LPIRR can yield a better solution, execution of algorithms with large k values would require excessively long running time. The parameter k of LCA is set to 3, and the algorithm is denoted as LCA-3. The parameter k of LPIRR is set to 3 and 4, and the corresponding algorithms are denoted as LPIRR-3 and LPIRR-4, respectively. All experiments are performed on a PC with four 3.20 GHz Intel Core i5 processors and 16 GB memory running CentOS 6.4. Except for LPIRR, the programs run sequentially on a single processor. LPIRR uses IBM CPLEX, a multithread-based software package.

Evaluating the performance of the proposed strategies

To evaluate the performance of the strategies, the

A VG_PR_ERR

BEST_PR_ERR

, and

GEO_RT

of the algorithms for the set of instances TestCase are summarized in Table 4. As can be seen in SPH and DNH rows, SPH can obtain significantly better solutions and spend less running time than DNH. SPH is better than DNH at the construction role in SPCF algorithms. The *_SPCH-I and *_SPCH-II rows confirm that SPSH strategies can significantly improve the quality of the solutions obtained by the classic heuristics.

A VG_PR_ERR

obtained with DNH and SPH reduce from 16.87% to less than 10% and from 10.43% to about 8.7% by adopting SPSH strategies, respectively. MS_SPSF and MSP_SPSF spend more time than SS_SPSF for the larger spreading range and passing the bridges. The *_SPCH-III and *_SPCH-IV rows show that two EDP strategies effectively improve solution quality. EDP_KPE has better performance in terms of solution quality than EDP_RS and spends more running time. The *_SPCH-VII, *_SPCH-VIII, and *_SPCH-IX rows indicate that all IS strategies improve solution quality significantly, and the

A VG_PR_ERR

reduces from about 8% to 3%. Among the three strategies, IS-I is the most time consuming but it has the best performance, and IS-III has the worst performance but it is the fastest strategy. The IS-I strategy of *_SPCH-V and *_SPCH-VI adopts the corresponding EDP strategy. As seen in *_SPCH-V and *_SPCH-VI rows, *_SPCH-V and *_SPCH-VI generate significantly better results than other SPCF algorithms, but they consume much more time. The

BEST_PR_ERR

of the algorithms indicates that the solutions of the SPH and SS_SPSH are sensitive to the selection of starting terminal, and we can obtain much better solutions by using the multi-start strategy. An effective tradeoff between solution quality and computing speed is achieved by employing the different combinations of the proposed strategies in line with the SPCF framework.

Table 4.

$A VG_PR_ERR$ , $BEST_PR_ERR$ , and $GEO_RT$ of the nine groups of SPCF algorithms on TestCase instances.

Algorithm	AVG_PR_ERR	BEST_PR_ERR	GEO_RT
DNH	16.87	–	1.75
SPH	10.43	7.1	1.73
MSP_SPCF-I	9.47	–	16.88
MSP_SPCF-II	8.76	7.37	15.84
MSP_SPCF-III	8.43	7.04	17.16
MSP_SPCF-IV	6.83	6.83	20.51
MSP_SPCF-V	1.34	0.93	109.46
MSP_SPCF-VI	1.59	0.85	72.72
MSP_SPCF-VII	2.20	1.36	51.99
MSP_SPCF-VIII	2.98	1.82	29.39
MSP_SPCF-IX	3.94	2.33	27.62
MS_SPCF-I	9.4	–	7.07
MS_SPCF-II	8.67	7.28	6.54
MS_SPCF-III	8.42	6.98	7.68
MS_SPCF-IV	7.72	6.76	9.98
MS_SPCF-V	1.33	0.87	88.84
MS_SPCF-VI	1.59	0.83	56.57
MS_SPCF-VII	2.18	1.37	38.05
MS_SPCF-VIII	2.96	1.79	17.01
MS_SPCF-IX	3.95	2.38	15.98
SS_SPCF-I	9.18	6.64	4.02
SS_SPCF-II	8.63	6.13	3.02
SS_SPCF-III	8.4	6.07	4.02
SS_SPCF-IV	7.74	5.87	5.53
SS_SPCF-V	1.33	0.54	100.32
SS_SPCF-VI	1.57	0.48	60.00
SS_SPCF-VII	2.24	0.85	36.97
SS_SPCF-VIII	3.01	1.08	12.22
SS_SPCF-IX	3.96	1.96	11.64

Comparison with other approaches

Five typical algorithms^{12,14,15,27,28} are compared with the proposed SS_SPCF-V algorithm.

As shown in Table 5, SS_SPCF-V algorithm is the most practical algorithm among the compared algorithms. For ADH, the solution can pass through the hard-nodes by traversing all vertices of the graph. The experimental results confirm that ADH obtains a much better solution than DNH and SPH. SS_SPCF-V requires only one-tenth of the running time of ADH and generates better solutions than those obtained by ADH. KBMPH has a little better performance in terms of solution quality than SPH and spends much more running time for constructing metric closure. It is a shortest path-based greedy method and the solution cannot pass through the hard-nodes. Although the parameter k of LCA and LPIRR are set to the minimal values, and the multithread technique is employed by LPIRR, the execution times of LCA and LPIRR are much longer than those of ADH and SS_SPCF-V. The solutions of LPIRRs and LCA-3 are poorer than ADH and SS_SPCF-V. The LPIRR-4 requires more than twice the running time of LPIRR-3 and can obtain better solutions. SS_SPCF-V algorithms obtain better solutions than the compared algorithms, with the exception of the DW algorithm. In addition, SS_SPCF-V algorithms are much faster than the compared algorithms, with the exception of DNH and SPH.

Table 5.

$A VG_PR_ERR$ , $BEST_PR_ERR$ , and $GEO_RT$ of the comparison algorithms on TestCase instances.

Algorithm	AVG_PR_ERR	BEST_PR_ERR	GEO_RT
SS_SPCF-V	1.33	0.54	100.32
ADH	1.39	–	1310.65
LCA-3	5.26	–	2748.62
LPIRR-3	5.06	4	29911.75
LPIRR-4	3.08	2.2	70636.35
DW	0	–	67200.44
KBMPH	10.33	7.01	1315.68

Conclusion

In this study, we present a Steiner point candidate-based heuristic algorithm framework for the GSTP that consists of the Steiner point candidates ${SPC}_{I}$ marking procedure, Steiner tree constructing procedure to connect Steiner point candidates and terminals of the GSTP, detour paths elimination procedure, and the Steiner point candidates ${SPC}_{II}$ -based refining procedure. Several alternative strategies with different effectiveness and speed performance for each procedure are presented. Nine groups of SPCF algorithms are constituted, and the performance of the proposed strategies is evaluated experimentally. SS_SPCF-V, which is most effective algorithm of SPCF algorithms, is compared with five algorithms on TestCase instances. SS_SPCF-V greatly improves the solution quality of the classic algorithms with reasonable running time. Compared with ADH, LCA, KBMPH, and LPIRR, SS_SPCF-V achieves better solution quality with shorter running times. Thus, SPCF is an efficient and effective practical algorithm framework for the GSTP.

In future, an appropriate combination of the proposed strategies in line with SPCF can be developed for specific engineering application problems. The proposed algorithm framework can also be extended to efficiently solve GSTPs with constraints such as the delay-constraint in multiple destination routing and a via minimization constraint in the routing stage of VLSI.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Key Basic Research Special Foundation (NKBRSF) of China (No. 2011CB808000), by the National Natural Science Foundation of China (No. 71231003, No. 11271002) by the Natural Science Foundation of Fujian Province, China (No.2016J01754), by the Educational Commission of Fujian Province of China (No. JA15069), by the Research Foundation of Fuzhou University (No. XRC-1557).

Appendix 1

TestCase class consists of 389 instances, of which numbers of the terminals are not more than 20 and numbers of the vertices are not more than 1000, from SteinLib. The names of the TestCase instances are presented below:

B01,B02,B04,B05,B07,B08,B10,B11,B13,B16,C01,C02,C06,C07,C11,C12,C16,C17,D01,D02,D06,D07,D11,D12,D16,D17,DIW0250,DIW0260,DIW0313,DIW0393,DIW0460,DIW0495,DIW0513,DIW0540,DMXA0296,DMXA0628,DMXA0734,DMXA0848,DMXA0903,DMXA1109,DMXA1304,DMXA1516,es10fst01,es10fst02,es10fst03,es10fst04,es10fst05,es10fst06,es10fst07,es10fst08,es10fst09,es10fst10,es10fst11,es10fst12,es10fst13,es10fst14,es10fst15,es20fst01,es20fst02,es20fst03,es20fst04,es20fst05,es20fst06,es20fst07,es20fst08,es20fst09,es20fst10,es20fst11,es20fst12,es20fst13,es20fst14,es20fst15,GAP1307,GAP1413,GAP1500,GAP1810,GAP2800,GAP2975,GAP3036,GAP3100,i320-001,i320-002,i320-003,i320-004,i320-005,i320-011,i320-012,i320-013,i320-014,i320-015,i320-021,i320-022,i320-023,i320-024,i320-025,i320-031,i320-032,i320-033,i320-034,i320-035,i320-041,i320-042,i320-043,i320-044,i320-045,i320-101,i320-102,i320-103,i320-104,i320-105,i320-111,i320-112,i320-113,i320-114,i320-115,i320-121,i320-122,i320-123,i320-124,i320-125,i320-131,i320-132,i320-133,i320-134,i320-135,i320-141,i320-142,i320-143,i320-144,i320-145,i080-001,i080-002,i080-003,i080-004,i080-005,i080-011,i080-012,i080-013,i080-014,i080-015,i080-021,i080-022,i080-023,i080-024,i080-025,i080-031,i080-032,i080-033,i080-034,i080-035,i080-041,i080-042,i080-043,i080-044,i080-045,i080-101,i080-102,i080-103,i080-104,i080-105,i080-111,i080-112,i080-113,i080-114,i080-115,i080-121,i080-122,i080-123,i080-124,i080-125,i080-131,i080-132,i080-133,i080-134,i080-135,i080-141,i080-142,i080-143,i080-144,i080-145,i080-201,i080-202,i080-203,i080-204,i080-205,i080-211,i080-212,i080-213,i080-214,i080-215,i080-221,i080-222,i080-223,i080-224,i080-225,i080-231,i080-232,i080-233,i080-234,i080-235,i080-241,i080-242,i080-243,i080-244,i080-245,i080-301,i080-302,i080-303,i080-304,i080-305,i080-311,i080-312,i080-313,i080-314,i080-315,i080-321,i080-322,i080-323,i080-324,i080-325,i080-331,i080-332,i080-333,i080-334,i080-335,i080-341,i080-342,i080-343,i080-344,i080-345,i160-001,i160-002,i160-003,i160-004,i160-005,i160-011,i160-012,i160-013,i160-014,i160-015,i160-021,i160-022,i160-023,i160-024,i160-025,i160-031,i160-032,i160-033,i160-034,i160-035,i160-041,i160-042,i160-043,i160-044,i160-045,i160-101,i160-102,i160-103,i160-104,i160-105,i160-111,i160-112,i160-113,i160-114,i160-115,i160-121,i160-122,i160-123,i160-124,i160-125,i160-131,i160-132,i160-133,i160-134,i160-135,i160-141,i160-142,i160-143,i160-144,i160-145,i640-001,i640-002,i640-003,i640-004,i640-005,i640-011,i640-012,i640-013,i640-014,i640-015,i640-021,i640-022,i640-023,i640-024,i640-025,i640-031,i640-032,i640-033,i640-034,i640-035,i640-041,i640-042,i640-043,i640-044,i640-045,lin01,lin02,lin03,lin04,lin05,lin06,lin07,lin08,lin09,lin10,lin11,lin12,lin13,MSM0580,MSM1008,MSM1234,MSM1707,MSM1844,MSM1931,MSM2000,MSM2326,MSM3676,MSM4038,MSM4114,MSM4190,MSM4224,MSM4414,MSM4515,P455,P456,P457,P458,P459,P460,P463,P464,P401,P402,P403,P404,P405,P406,P407,P408,cc3-4p,cc3-4u,cc3-5p,cc3-5u,cc6-2p,cc6-2u,P619,P620,P621,P622,P623,P624,P625,P626,P630,P631,P602,P603,P604,P605,P606,P607,P608,P609,P613,P614,antiwheel5,design432,oddcycle3,oddwheel3,se03,TAQ0023,TAQ0631,TAQ0739,TAQ0741,TAQ0891,TAQ0910,TAQ0920,TAQ0978,BERLIN52.

References

Castro

. Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems. J Heurist 2013; 19: 317–342.

Leung

Z-B

. A genetic algorithm for the multiple destination routing problems. IEEE Trans Evol Comput 1998; 2: 150–161.

Wen-Liang Z, Jian H and Jun Z. A novel particle swarm optimization for the Steiner tree problem in graphs. In: IEEE congress on evolutionary computation, Hong Kong, China, 1–6 June 2008, pp.2460–2467. New York: IEEE.

Long

Zhou

Memik

. EBOARST: an efficient edge-based obstacle-avoiding rectilinear Steiner tree construction algorithm. IEEE Trans Comput-Aid Des Integrat Circ Syst 2008; 27: 2169–2182.

Ajwani

Chu

Mak

W-K

. FOARS: FLUTE based obstacle-avoiding rectilinear Steiner tree construction. IEEE Trans Comput-Aid Des Integrat Circ Syst 2011; 30: 194–204.

Santambrogio

LBF

. An equivalent path functional formulation of branched transportation problems. Discret Contin Dyn Syst A 2011; 29: 845–871.

Wolansky

. Limit theorems for optimal mass transportation and applications to networks. Discret Contin Dyn Syst A 2011; 30: 365–374.

Zhang

Dong

Frank Chen

. A bottleneck Steiner tree based multi-objective location model and intelligent optimization of emergency logistics systems. Robot Comput-Integrat Manuf 2013; 29: 48–55.

Xue

Lillys

Dougherty

. Computing the minimum cost pipe network interconnecting one sink and many sources. SIAM J Optimiz 1999; 10: 22–42.

10.

Gonçalves

Gouveia

Pato

. An improved decomposition-based heuristic to design a water distribution network for an irrigation system. Ann Oper Res 2011; 2011: 1–27.

11.

Karp

Reducibility among combinatorial problems. In: Jünger

Liebling

Naddef

(eds). 50 years of integer programming 1958–2008, Berlin: Springer Berlin Heidelberg, 2010, pp. 219–241.

12.

Dreyfus

Wagner

. The steiner problem in graphs. Networks 1972; 1: 195–207.

13.

Polzin

Daneshmand

. Improved algorithms for the Steiner problem in networks. Discrete Appl Math 2001; 112: 263–300.

14.

Robins

Zelikovsky

. Tighter bounds for graph Steiner tree approximation. SIAM J Discret Math 2005; 19: 122–134.

15.

Byrka

Grandoni

Rothvoss

. Steiner tree approximation via iterative randomized rounding. J ACM 2013; 60: 1–33.

16.

Takahashi

Matsuyama

. An approximate solution for the Steiner problem in graphs. Math Japon 1980; 6: 573–577.

17.

Kou

Markowsky

Berman

. A fast algorithm for Steiner trees. Acta Inform 1981; 15: 141–145.

18.

Rayward-Smith

. The computation of nearly minimal Steiner trees in graphs. Int J Math Educ Sci Technol 1983; 14: 15–23.

19.

Duin

Voβ

. Efficient path and vertex exchange in steiner tree algorithms. Networks 1997; 29: 89–105.

20.

Ribeiro

De Souza

. Tabu search for the Steiner problem in graphs. Networks 2000; 36: 138–146.

21.

de Aragao MP, Ribeiro CC, Uchoa E, et al. Hybrid local search for the Steiner problem in graphs. In: Extended abstracts of the 4th metaheuristics international conference, Porto, Portugal, August 2001, pp.429–433.

22.

Uchoa

Werneck

. Fast local search for the steiner problem in graphs. J Exp Algorithm 2012; 17: 2.1–2.22.

23.

Duin

Volgenant

. Reduction tests for the steiner problem in graphs. Networks 1989; 19: 549–567.

24.

Polzin

Daneshmand

Extending reduction techniques for the Steiner tree problem. In: Möhring

Raman

(eds). Algorithms — ESA 2002 2002; Vol. 2461, Berlin: Springer Berlin Heidelberg, pp. 795–807.

25.

Kingston

Sheppard

. On reductions for the Steiner problem in graphs. J Discret Algorith 2003; 1: 77–88.

26.

Lin

Chen

S-Y

Chi-Feng

. Obstacle-avoiding rectilinear Steiner tree construction based on spanning graphs. IEEE Trans Comput-Aid Des Integrat Circ Syst 2008; 27: 643–653.

27.

Yan-Ping

Pei-liang

. An improved algorithm for Steiner trees. J China Inst Commun 2002; 23: 35–40.

28.

Rayward-Smith

Clare

. On finding steiner vertices. Networks 1986; 16: 283–294.

29.

Koch

Martin

Voß

. SteinLib: an updated library on Steiner tree problems in graphs, Berlin: Konrad-Zuse-Zentrum fix ur Informationstechnik Berlin, 2000.

30.

Mehlhorn

. A faster approximation algorithm for the Steiner problem in graphs. Inform Process Lett 1988; 27: 125–128.

31.

Aragão

Werneck

On the implementation of MST-based heuristics for the Steiner problem in graphs. In: Mount

Stein

(eds). Algorithm engineering and experiments 2002; Vol. 2409, Berlin: Springer Berlin Heidelberg, pp. 1–15.

32.

Young

EFY

. Obstacle-avoiding rectilinear Steiner tree construction. IEEE Trans Comput-Aid Des Integrat Circ Syst 2008; 27: 523–528.

33.

Liu

C-H

Kuo

S-Y

Lee

. Obstacle-avoiding rectilinear Steiner tree construction: a Steiner-point-based algorithm. IEEE Trans Comput-Aid Des Integrat Circ Syst 2012; 31: 1050–1060.

34.

Skorin-Kapov

Kos

. A GRASP heuristic for the delay-constrained multicast routing problem. Telecommun Syst 2006; 32: 55–69.

35.

Widmayer

Wong

. A faster approximation algorithm for the Steiner problem in graphs. Acta Inform 1986; 23: 223–229.

36.

Ying-Fung

Widmayer

Schlag

MDF

. Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacles. IEEE Trans Comput 1987; 36: 321–331.

37.

Robins

Zelikovsky

Minimum Steiner tree construction. In: Alpert

Mehta

Sapatnekar

(eds). Handbook of algorithms for physical design automation, Boca Raton, FL: CRC Press, 2009, pp. 487–508.

38.

Cormen

Leiserson

Rivest

. Introduction to algorithms, 3rd ed. Cambridge: MIT Press, 2009.

39.

Lawler

The Steiner problem and other dilemmas. In: Holt

RAW

(ed). Combinatorial optimization: networks and matroids, New York: Dover Publication, 1976, pp. 290–296.

A Steiner point candidate-based heuristic framework for the Steiner tree problem in graphs

Abstract

Keywords

Introduction

Preliminaries

Steiner tree problem in graphs

Definition 1

Voronoi diagram and construction

Definition 2

Property 1

Classic heuristic algorithms

DNH

SPH

Shortest paths and Steiner point candidates

Property 2

Proof

Definition 3

Property 3

Steiner point candidate-based heuristic algorithms

Marking the Steiner point candidates SPC I

Definition 4

Single source shortest path cluster heuristic

Property 4

Proof

Multi-source shortest path cluster heuristic

Property 5

Proof

Multi-source parallel shortest path cluster heuristic

Property 6

Proof

Construction algorithms

Eliminating the detour paths

SPCII-based refining strategies

Definition 5

Property 7

Proof

Property 8

Proof

Property 9

Proof

Property 10

Main framework of the SPCF

Computational experiments

Evaluating the performance of the proposed strategies

Comparison with other approaches

Conclusion

Footnotes

Declaration of conflicting interests

Funding

Appendix 1

References

Marking the Steiner point candidates ${SPC}_{I}$

SPC_II-based refining strategies