We study a reconfiguration problem for Steiner trees in an unweighted graph, which determines whether there exists a sequence of Steiner trees that transforms a given Steiner tree into another one by exchanging a single edge at a time. In this paper, we show that the problem is PSPACE-complete even for split graphs, while solvable in linear time for interval graphs and for cographs.

The Steiner tree problem is a nondeterministic-polynomial-time-complete problem, so heuristic polynomial-time algorithms have been proposed for finding multicast trees. However, these polynomial-time algorithms' tree-cost optimality rates are not sufficient to obtain effective multicast trees, so intelligence algorithms, such as the genetic algorithm and artificial fish swarm algorithm, were proposed to improve previously proposed polynomial-time algorithms. However, these intelligence algorithms are time-consuming, even though they can reach quasi-optimal multicast trees. This paper proposes the multi-agent branch-based multicast (BBMC) algorithm, which can maintain the fast speed of polynomial-time algorithms while matching the tree-cost optimality of intelligence algorithms. The advantage of the proposed multi-agent BBMC algorithm is its covering of discarded effective branch candidates to seek the optimal multicast tree. By saving these branch candidates, the algorithm incurs tree-costs that are as small as those of intelligence algorithms, and by saving only a limited number of effective candidates, the algorithm is much faster than intelligence algorithms.

The 3-D channel routing is a fundamental problem on the physical design of 3-D integrated circuits. The 3-D channel is a 3-D grid G and the terminals are vertices of G located in the top and bottom layers. A net is a set of terminals to be connected. The objective of the 3-D channel routing problem is to connect the terminals in each net with a Steiner tree (wire) in G using as few layers as possible and as short wires as possible in such a way that wires for distinct nets are disjoint. This paper shows that the problem is intractable. We also show that a sparse set of ν 2-terminal nets can be routed in a 3-D channel with O(√ν) layers using wires of length O(√ν).

In this paper we discuss approximation algorithms for the ELEMENT-DISJOINT STEINER TREE PACKING problem (Element-STP for short). For a graph G=(V,E) and a subset of nodes T⊆V, called terminal nodes, a Steiner tree is a connected, acyclic subgraph that contains all the terminal nodes in T. The goal of Element-STP is to find as many element-disjoint Steiner trees as possible. Element-STP is known to be APX-hard even for |T|=3 [1]. It is also known that Element-STP is NP-hard to approximate within a factor of Ω(log |V|) [3] and there is an O(log |V|)-approximation algorithm for Element-STP [2],[4]. In this paper, we provide a $lceil rac{|T|}{2} ceil$-approximation algorithm for Element-STP on graphs with |T| terminal nodes. Furthermore, we show that the approximation ratio of 3 for Element-STP on graphs with five terminal nodes can be improved to 2.

This paper presents an artificial fish swarm algorithm (AFSA) to solve the multicast routing problem, which is abstracted as a Steiner tree problem in graphs. AFSA adopts a 0-1 encoding scheme to represent the artificial fish (AF), which are then subgraphs in the original graph. For evaluating each AF individual, we decode the subgraph into a Steiner tree. Based on the adopted representation of the AF, we design three AF behaviors: randomly moving, preying, and following. These behaviors are organized by a strategy that guides AF individuals to perform certain behaviors according to certain conditions and circumstances. In order to investigate the performance of our algorithm, we implement exhaustive simulation experiments. The results from the experiments indicate that the proposed algorithm outperforms other intelligence algorithms and can obtain the least-cost multicast routing tree in most cases.

There is a well known Steiner tree algorithm called minimum-cost paths heuristic (MPH), which is used for many multicast network operations and is considered a benchmark for other Steiner tree algorithms. MPH's average case time complexity is O(m(l+nlog n)), where m is the number of end nodes, n is the number of nodes, and l is the number of links in the network, because MPH has to run Dijkstra's algorithm as many times as the number of end nodes. The author recently proposed a Steiner tree algorithm called branch-based multi-cast (BBMC), which produces exactly the same multicast tree as MPH in a constant processing time irrespective of the number of multicast end nodes. However, the theoretical result for the average case time complexity of BBMC was expressed as O(log m(l+nlog n)) and could not accurately reflect the above experimental result. This paper proves that the average case time complexity of BBMC can be shortened to O(l+nlog n), which is independent of the number of end nodes, when there is an upper limit of the node degree, which is the number of links connected to a node. In addition, a new parameter β is applied to BBMC, so that the multicast tree created by BBMC has less links on it. Even though the tree costs increase due to this parameter, the tree cost increase rates are much smaller than the link decrease rates.

We propose novel tree construction algorithms for multicast communication in photonic networks. Since multicast communications consume many more link resources than unicast communications, effective algorithms for route selection and wavelength assignment are required. We propose a novel tree construction algorithm, called the Weighted Steiner Tree (WST) algorithm and a variation of the WST algorithm, called the Composite Weighted Steiner Tree (CWST) algorithm. Because these algorithms are based on the Steiner Tree algorithm, link resources among source and destination pairs tend to be commonly used and link utilization ratios are improved. Because of this, these algorithms can accept many more multicast requests than other multicast tree construction algorithms based on the Dijkstra algorithm. However, under certain delay constraints, the blocking characteristics of the proposed Weighted Steiner Tree algorithm deteriorate since some light paths between source and destinations use many hops and cannot satisfy the delay constraint. In order to adapt the approach to the delay-sensitive environments, we have devised the Composite Weighted Steiner Tree algorithm comprising the Weighted Steiner Tree algorithm and the Dijkstra algorithm for use in a delay constrained environment such as an IPTV application. In this paper, we also give the results of simulation experiments which demonstrate the superiority of the proposed Composite Weighted Steiner Tree algorithm compared with the Distributed Minimum Hop Tree (DMHT) algorithm, from the viewpoint of the light-tree request blocking.

In this paper, we propose a network-aware overlay multicast (NAOM) technique for large data dissemination in a well-managed overlay network. To improve the throughput, NAOM utilizes forward-only hosts; these hosts participate in the overlay network but are not members of the multicast. With the inclusion of the forward-only hosts, data slices can detour bottleneck links and more resources can be used to build efficient multicast trees. Large data are divided into fixed-size slices, and the slices are delivered simultaneously to multicast receivers along the multiple multicast trees. We model the problem of building efficient multicast trees with the inclusion of forward-only hosts. The problem is an NP-hard problem, and we introduce a polynomial time heuristic algorithm. Furthermore, we propose a dynamic scheduling scheme for the transfer of data along the evaluated multicast trees. Our experimental results in a real network environment show an improvement of the throughput but at the cost of additional resource consumption of forward-only nodes.

We have been developing a secure and reliable distributed storage system, which uses a secret sharing scheme. In order to efficiently store data in the system, this paper introduces an optimal share transfer problem, and proves it to be, generally, NP-hard. It is also shown that the problem can be resolved into a Steiner tree problem. Finally, through computational experiments we perform the comparison of heuristic algorithms for the Steiner tree problem.

As the complexity of VLSI circuits increases, the routability problem becomes more and more important in modern VLSI design. In general, the flexibility improvement of the edges in a routing tree has been exploited to release the routing congestion and increase the routability in the routing stage. Given an initial rectilinear Steiner tree, the rectilinear Steiner tree can be transformed into a Steiner routing tree by deleting all the corner points in the rectilinear Steiner tree. Based on the definition of the routing flexibility in a Steiner routing tree and the timing-constrained location flexibility of the Steiner-point in any Y-type wire, the simulated-annealing-based approach is proposed to construct a better timing-constrained flexibility-driven Steiner routing tree by reassigning the feasible locations of the Steiner points in all the Y-type wires. The experimental results show that our proposed algorithm, STFSRT, can increase about 0.005-0.020% wire length to improve about 43-173% routing flexibility for the tested benchmark circuits.

Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. In this paper, we investigate the Steiner tree problem in distributed systems, and propose a self-stabilizing heuristic solution to the problem. Our algorithm is constructed by four layered modules (sub-algorithms): construction of a shortest path forest, transformation of the network, construction of a minimum spanning tree, and pruning unnecessary links and processes. Competitiveness is 2(1-1/l), where l is the number of leaves of optimal solution.

As a remarkable development of VLSI technology, a gate switching delay is reduced and a signal delay of a net comes to have a considerable effect on the clock period. Therefore, it is required to minimize signal delays in digital VLSIs. There are a number of ways to evaluate a signal delay of a net, such as cost, radius, and Elmore's delay. Delays of those models can be computed in linear time. Elmore's delay model takes both capacitance and resistance into account and it is often regarded as a reasonable model. So, it is important to investigate the properties of this model. In this paper, we investigate the properties of the model and construct a heuristic algorithm based on these properties for computing a wiring of a net to minimize the interconnection delay. We show the effectiveness of our proposed algorithm by comparing ERT algorithm which is proposed in [2] for minimizing the maximum Elmore's delay of a sink. Our proposed algorithm decreases the average of the maximum Elmore's delay by 10-20% for ERT algorithm. We also compare our algorithm with an O(n4) algorithm proposed in [15] and confirm the effectiveness of our algorithm though its time complexity is O(n3).

In this paper, we are concerned in obtaining multicast trees in packet-switched networks such as ATM nets, when there exist constraints on the packet (cell)-replication capabilities of the individual switching nodes. This problem can be formulated as the Steiner tree problem with degree bounds on the nodes, so we call it the Degree-Constrained Steiner Tree problem (DCST). Four heuristic algorithms are proposed: the first is a combined version of two well-known Steiner tree algorithms, heuristic Naive and the shortest path heuristic (SPH), and the second is a relaxation algorithm based on a mathematical formulation of the DCST, and the last two use a tree reconfiguration scheme based on the concept of 'logical link. ' We experimentally compare our algorithms with the previous ones in three respects; number of solved instances, objective value or tree cost, and computation time. The experimental results show that there are few instances unsolved by our algorithms, and the objective values are mostly within 5% of optimal. Computation times are also acceptable.

A reallocation problem is defined as determining whether blocks can be moved from their current boxes to their destination boxes in the number of moves less than or equal to a given positive integer. This problem is defined simply and has many practical applications. We previously proved the following results: The reallocation problem such that the block volume is restricted to one volume unit for all blocks can be solved in linear time. But the reallocation problem such that the block volume is not restricted is NP-complete, even if no blocks have bypass boxes. But the computational complexity of the reallocation problems such that the range of the block volume is restricted has not yet been known. We prove that the reallocation problem is NP-complete even if the block volume is restricted to one or two volume units for all blocks and no blocks have bypass boxes. Furthermore, we prove that the reallocation problem is NP-complete, even if there are only two blocks such that each block has the volume units of fixed positive integer greater or equal than two, the volume of the other blocks is restricted to one volume unit, and no blocks have bypass boxes. Next, we consider such a block that must stays in a same box both in the initial state and in the final state but can be moved to another box for making room for other blocks. We prove that the reallocation problem such that an instance has such blocks is also NP-complete even if the block volume is restricted to one volume unit for all blocks.

We survey recent developments in the study of approximation algorithms for NP-hard geometric optimization problems. We focus on those problems which, given a set of points, ask for a graph of a specified type on those points with the minimum total edge length, such as the traveling salesman problem, the Steiner minimum tree problem, and the k-minimum spanning tree problem. In a recent few years, several polynomial time approximation schemes are discovered for these problems. All of them are dynamic programming algorithms based on some geometric theorems that assert the existence of a good approximate solution with a simple recursive decomposition structure. Our emphasis is on these geometric theorems, which have potential uses in the design and analysis of heuristic algorithms.

A problem of obtaining an optimal file transfer on a file transmission net N is to consider how to distribute, with a minimum total cost, copies of a certain file of information from some vertices to others on N by the respective vertices' copy demand numbers. This paper proves such a problem to be NP-hard in general.

This paper studies the routing algorithms for multi-destination connections where each destination may require different amount of data streams. This asymmetric feature can arise mostly in a large and/or heterogeneous network environment. There are mainly two reasons for this. One is that terminal equipments may have different capabilities. The other is that users may have various interests in the same set of information. We first define the asymmetric multicast problem and describe an original routing method for this type of multicast. The method is then employed in the presented routing algorithms, which can be run in multi-cluster environment. The multi-cluster architecture is considered to be effective for running routing in the networks, where a variety of operating methods might be applied in different clusters but global network performance is required. Our algorithms are designed based on some classical Steiner tree heuristics. The basic goal of our algorithms is to make routing decisions for the asymmetric multicast connections with minimum-cost purpose. In addition, we also consider delay constraint requirements in the multicast connections and propose correspondent algorithms. We compare the performance between SPT (Shortest Path Tree)-based algorithms and the presented algorithms by simulations. We show that performance difference exists among the different types of the algorithms.

The most crucial factor that degrades a high speed VLSI is the signal propagation delay in a routing tree. It is estimated by the sum of the delay caused by the source-to-sink path length and by the total length. To design a routing tree in which these two are both small and balanced, we propose an algorithm to construct such a spanning tree, based on the idea of constructing a tree combining the minimum-spanning-tree and shortest-path-tree algorithms. This idea is extended to finding a rectilinear Steiner tree. Experiments are presented to illustrate how the source-to-sink path length and total length can be ballanced and small.