1. On oriented diameter of [formula omitted]-star graphs.
- Author
-
Ajish Kumar, K.S., Sasidharan, Birenjith, and Sudeep, K.S.
- Subjects
- *
DIRECTED graphs , *ROUTING algorithms , *DISTRIBUTED algorithms , *UNDIRECTED graphs , *DIAMETER , *TOPOLOGY - Abstract
Assignment of one of two possible directions to every edge of an undirected graph G = (V , E) is called an orientation of G. The resulting directed graph is denoted by G ⃗. A strong orientation is one in which every vertex is reachable from every other vertex via a directed path in G ⃗. The diameter of G ⃗ , i.e., the maximum distance from any vertex to any other vertex, depends on the particular orientation. The minimum diameter among all possible orientations of G is called the oriented diameter diam ⃗ (G) of G. Let n , k be two integers such that 1 ≤ k < n. In the realm of interconnection networks of processing elements, an (n , k) -star graph S n , k offers a topology that permits to circumvent the lack of scalability of n -star graphs S n. The oriented diameter quantifies an upper limit on the delay in communication over interconnection networks. In this paper, we present a strong orientation scheme for S n , k that combines approaches suggested by Cheng and Lipman (2002) for S n , k with the one proposed by Fujita (2013) for S n , reaping benefits from both worlds. Next, we propose a distributed routing algorithm for S n , k ⃗ inspired by an algorithm proposed in Kumar et al. (2021) for S n ⃗. With the aid of both the orientation scheme and the routing algorithm, we show that diam ⃗ (S n , k) ≤ ⌊ n + k 2 ⌋ + 2 k + 6 − δ (n , k) where δ (n , k) is a non-negative function. The function δ (n , k) takes on values 2 k − n , 0 , and n − 3 k 2 respectively for three disjoint intervals k > n 2 , n 3 < k ≤ n 2 and k ≤ n 3 . For every value of n , k , our upper bound performs better than all known bounds in literature. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF