Narrow Results

Let $G=(V,E,w,\rho ,X)$ be a weighted undirected connected graph, where $V$ is the set of vertices, $E$ is the set of edges, $X\subseteq V$ is a subset of terminals, $w(e)>0,\forall e\in E$ denotes the weight associated with edge $e$, and $\rho (v)>0,\forall v\in V$ denotes the weight associated with vertex $v$. Let $T$ be a Steiner tree in $G$ to interconnect all terminals in $X$. For any two terminals, $t^{\prime },t^{″}\in X$, we consider the weighted tree distance on $T$ from $t^{\prime }$ to $t^{″}$, defined as the weight of $t^{″}$ times the classic tree distance on $T$ from $t^{\prime }$ to $t^{″}$. The longest weighted tree distance on $T$ between terminals is named the weighted diameter of $T$. The Minimum Diameter Vertex-Weighted Steiner Tree Problem (MDWSTP) asks for a Steiner tree in $G$ of the minimum weighted diameter to interconnect all terminals in $X$. In this paper, we introduce two classes of parameterized graphs (PG), $〈X,\mu 〉$-PG and $(X,\lambda )$-PG, in terms of the parameterized upper bound on the ratio of two vertex weights, and a weaker version of the parameterized triangle inequality, respectively, and present approximation algorithms of a parameterized factor for the MDWSTP in them. For the MDWSTP in an edge-weighted $〈X,\mu 〉$-PG, we present an approximation algorithm of a parameterized factor $\frac{\mu +1}{2}$. For the MDWSTP in a vertex-weighted $(X,\lambda )$-PG, we first present a simple approximation algorithm of a parameterized factor $\lambda$, where $\lambda$ is tight when $\lambda \ge 2$, and further develop another approximation algorithm of a slightly improved factor.

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 $\mathrm{\Theta }(\mathrm{\text{min}}\{logk,m\})$ on the competitive ratio for this problem, where $k$ is the total number of nodes to be connected and $m$ is the total number of different bursts. In directed graphs of bounded edge asymmetry $\alpha$, we provide a competitive ratio for this problem with a gap of ${𝒪}(\mathrm{\text{min}}\{\alpha ,m\})$ factor between the lower bound and the upper bound. We also show that a tight bound of $\mathrm{\Theta }(\mathrm{\text{min}}\{logk,m\})$ 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.

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 $Õ(n^{1/3})$ rounds and $Õ(n^{7/3})$ messages for a given connected undirected weighted graph of $n$ nodes. Note here that $Õ(\cdot )$ notation hides polylogarithmic factors in $n$. The second one computes a Steiner tree using $O(S+loglogn)$ rounds and $O(Sm+n^2)$ messages, where $S$ and $m$ are the shortest path diameter and number of edges respectively in the given input graph. Both the algorithms achieve an approximation ratio of $2(1-1/\ell )$, where $\ell$ is the number of leaf nodes in the optimal Steiner tree. For graphs with $S=\omega (n^{1/3}logn)$, the first algorithm exhibits better performance than the second one in terms of the round complexity. On the other hand, for graphs with $S=õ(n^{1/3})$, the second algorithm outperforms the first one in terms of the round complexity. In fact when $S=O(loglogn)$ then the second algorithm achieves a round complexity of $O(loglogn)$ and message complexity of $Õ(n^2)$. To the best of our knowledge, this is the first work to study the Steiner tree problem in the CCM.

The two-server problem is concerned with the movement of two servers to request points in a metric space. We consider an offline version of the problem in a graph in which the requests may be served in any order. A family of approximations algorithms is developed for this NP-complete problem.

In this paper we study the Station Placement problem on directed graphs, a problem that has applications to efficient multicasting in circuit-switched networks. We first argue that the problem on general directed graphs can be efficiently reduced to computing bounded depth Steiner tree on complete weighted directed graphs. Then, we concentrate on the case in which the graph is a directed tree and we give polynomial time algorithms to solve the problem and a natural variant of the problem.

Distance hereditary graphs are graphs in which every two vertices have the same distance in every connected induced subgraph containing them. In this paper, we study properties of distance hereditary graphs from the view point of parallel computations. We present efficient parallel algorithms for finding a minimum weighted connected dominating set, a minimum weighted Steiner tree, which take O(log n) time using O(n + m) processors on CRCW PRAM, where n and m are the number of vertices and edges of a given graph, respectively. We also find a maximum weighted clique of a distance hereditary graph in O(log² n) time using O(n + m) processors on a CREW PRAM.

The Steiner distance of a graph, introduced by Chartrand, Oellermann, Tian and Zou in 1989, is a natural generalization of the concept of classical graph distance. For a connected graph G of order at least 2 and $S\subseteq V(G)$, the Steiner distance d_G(S) among the vertices of S is the minimum size among all connected subgraphs whose vertex sets contain S. Let n, k be two integers with 2 ≤ k ≤ n. Then the Steiner k-eccentricity e_k(v) of a vertex v of G is defined by $e_k\mathrm{(v)=}\text{max}\left\{d\right(S)\hspace{0.17em}|\hspace{0.17em}S\hspace{0.17em}\subseteq \hspace{0.17em}\mathrm{V(G),}\hspace{0.17em}\hspace{0.17em}\mathrm{|S|=k,}\hspace{0.17em}\hspace{0.17em}\text{and}\hspace{0.17em}v\hspace{0.17em}\in \hspace{0.17em}S\}$. Furthermore, the Steiner k-diameter of G is $sdia{m}_k\left(G\right)=max\left\{e_k\left(v\right)\right|v\in V\left(G\right)\}$. In 2011, Chartrand, Okamoto and Zhang showed that k − 1 ≤ sdiam_k(G) ≤ n − 1. In this paper, graphs with sdiam₄(G) = 3, 4, n − 1 are characterized, respectively.

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.

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 ℓ₁- and ℓ₂-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.

We present a definition of characteristic area and inner spanning tree to accommodate the proof of Du and Hwang for Gilbert–Pollak conjecture on the Steiner ratio in the Euclidean plane.

Many models of genome rearrangement involve operations that are self-inverse, and hence generate a group acting on the space of genomes. This gives a correspondence between genome arrangements and the elements of a group, and consequently, between evolutionary paths and walks on the Cayley graph. Many common methods for phylogenetic reconstruction rely on calculating the minimal distance between two genomes; this omits much of the other information available from the Cayley graph. In this paper, we begin an exploration of some of this additional information, in particular describing the phylogeny as a Steiner tree within the Cayley graph, and exploring the “interval” between two genomes. While motivated by problems in systematic biology, many of these ideas are of independent group-theoretic interest.

A graph $G$ is a 3-degree 4-chordal graph if every cycle of length at least five has a chord and the degree of each vertex is at most three. In this paper, we investigate the structure of 3-degree 4-chordal graphs, which is a subclass of 3-degree graphs. We present a structural characterization based on minimal vertex separators and bi-connected components. Many classical problems are known to be NP-complete for 3-degree graphs, and 3-degree 4-chordal graphs are a nontrivial subclass of 3-degree graphs. Using our structural results, we present polynomial-time algorithms for many classical problems which are grouped into (i) subset problems (vertex cover and its variants, feedback vertex set, Steiner tree), (ii) Hamiltonicity and its variants, (iii) graph embedding problems (treewidth, minimum fill-in), and (iv) Coloring problems(rainbow coloring).

For a connected graph $G$ of order $p$ and a set $S\subseteq V(G)$, the Steiner distance of $S$ is the minimum number of edges in a connected subgraph of $G$ containing $S$. If $n$ is an integer, $2\le n\le p$ and a vertex $v\in V(G)$, the Steiner $n$-eccentricity of a vertex $v$ of $G$, ${\mathrm{\text{ex}}}_n(v)$, is the maximum Steiner distance of all $n$-subsets of $V(G)$ containing $v$. The Steiner $n$-radius of $G$, ${\mathrm{\text{rad}}}_n(G)$, is the minimum Steiner $n$-eccentricities of all vertices in $G$. We give bounds on ${\mathrm{\text{rad}}}_n(G)$ in terms of the order of $G$ and the minimum degree of $G$ for all graphs and for graphs that contain no triangles. We shall also investigate the relation between the $n$-radius of a graph $G$ and its complement $Ḡ$.

The minimum Steiner tree problem has wide application background, such as transportation system, communication network, pipeline design and VISL, etc. It is unfortunately that the computational complexity of the problem is NP-hard. People are common to find some special problems to consider. Since the complexity of the Steiner tree problem, the almost of papers are relate to the object of small data problem, i.e., the number of involved objects is small. Those conclusions are useful to the theoretical research from which some algorithms are originated. For the practical problems, there are large number of objects are need to be considered. How to find the more optimal approximate algorithm is the reason of paper. We want to find the more optimal approximate approach by the analysis of the different cases.