JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13]


Journal of Information Science and Engineering, Vol. 35 No. 4, pp. 721-735


Steiner Distance in Join, Corona, Cluster, and Threshold Graphs


ZHAO WANG1, YAPING MAO2, CHRISTOPHER MELEKIAN3
AND EDDIE CHENG3
1School of Mathematical Sciences
Beijing Normal University
Beijing, P.R. China

2Department of Mathematics
Qinghai Normal University
Qinghai, P.R. China

3Department of Mathematics and Statistics
Oakland University
Oakland, MI, U.S.A.


For a connected graph G and a subset S of its vertices, the Steiner tree problem consists of finding a minimum-size connected subgraph containing S. The Steiner distance of S is the size of a Steiner tree for S, and the Steiner k-diameter of G is the maximum value of the Steiner distance over all vertex subsets S of cardinality k. Calculation of Steiner trees and Steiner distance is known to be NP-hard in general, so applications may benefit from using graphs where the Steiner distance and structure of Steiner trees are known. In this paper, we investigate the Steiner distance and Steiner k-diameter of the join, corona, and cluster of connected graphs, as well as threshold graphs.


Keywords: wireless sensor networks, localization, mobile beacon, mobile anchor, RSSI

  Retrieve PDF document (JISE_201904_01.pdf)