The Clustered Selected-Internal Steiner Tree Problem

Abstract: Given a complete graph

G = (V, E)

, with nonnegative edge costs, two subsets

R s u b s e t V

and

R^{p r i m e} s u b s e t R

, a partition

m a t h c a l R = R_{1}, R_{2}, l d o t s, R_{k}

of

R

,

R_{i} c a p R_{j} = p h i

,

i e q j

and

m a t h c a l R^{p r i m e} = R_{1}^{p r i m e}, R_{2}^{p r i m e}, l d o t s, R_{k}^{p r i m e}

of

R^{p r i m e}

,

R_{i}^{p r i m e} s u b s e t R_{i}

, a clustered Steiner tree is a tree

T

of

G

that spans all vertices in

R

such that

T

can be cut into

k

subtrees

T_{i}

by removing

k - 1

edges and each subtree

T_{i}

spanning all vertices in

R_{i}

,

1 l e q i l e q k

. 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

G

is a clustered Steiner tree for

R

if all vertices in

R_{i}^{p r i m e}

are internal vertices of

T_{i}

,

1 l e q i l e q k

. The clustered selected-internal Steiner tree problem is concerned with the determination of a clustered selected-internal Steiner tree

T

for

R

and

R^{p r i m e}

in

G

with minimum cost. In this paper, we present the first known approximation algorithm with performance ratio

(h o + 4)

for the clustered selected-internal Steiner tree problem, where

h o

is the best-known performance ratio for the Steiner tree problem.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: The Clustered Selected-Internal Steiner Tree Problem