Search

Let G be a graph and W a subset of V(G). A subtree with the minimum number of edges that contains all vertices of W is a Steiner tree for W. The number of edges of such a tree is the Steiner distance of W and union of all vertices belonging to Steiner trees for W form a Steiner interval. We describe both of these for the lexicographic product of graphs. We also give a complete answer for the following invariants with respect to the Steiner convexity: the Steiner number, the rank, the hull number, and the Carathéodory number, and a partial answer for the Radon number. [ABSTRACT FROM AUTHOR]

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 $O(\frac{n^2}{\varepsilon^2})$ 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). [ABSTRACT FROM AUTHOR]