Back to Search
Start Over
Oriented diameter of star graphs
- Source :
- Discrete Applied Mathematics. 319:362-371
- Publication Year :
- 2022
- Publisher :
- Elsevier BV, 2022.
-
Abstract
- An {\em orientation} of an undirected graph $G$ is an assignment of exactly one direction to each edge of $G$. Converting two-way traffic networks to one-way traffic networks and bidirectional communication networks to unidirectional communication networks are practical instances of graph orientations. In these contexts minimising the diameter of the resulting oriented graph is of prime interest. The $n$-star network topology was proposed as an alternative to the hypercube network topology for multiprocessor systems by Akers and Krishnamurthy [IEEE Trans. on Computers (1989)]. The $n$-star graph $S_n$ consists of $n!$ vertices, each labelled with a distinct permutation of $[n]$. Two vertices are adjacent if their labels differ exactly in the first and one other position. $S_n$ is an $(n-1)$-regular, vertex-transitive graph with diameter $\lfloor 3(n-1)/2 \rfloor$. Orientations of $S_n$, called unidirectional star graphs and distributed routing protocols over them were studied by Day and Tripathi [Information Processing Letters (1993)] and Fujita [The First International Symposium on Computing and Networking (CANDAR 2013)]. Fujita showed that the (directed) diameter of this unidirectional star graph $\overrightarrow{S_n}$ is at most $\lceil{5n/2}\rceil + 2$. In this paper, we propose a new distributed routing algorithm for the same $\overrightarrow{S_n}$ analysed by Fujita, which routes a packet from any node $s$ to any node $t$ at an undirected distance $d$ from $s$ using at most $\min\{4d+4, 2n+4\}$ hops. This shows that the (directed) diameter of $\overrightarrow{S_n}$ is at most $2n+4$. We also show that the diameter of $\overrightarrow{S_n}$ is at least $2n$ when $n \geq 7$, thereby showing that our upper bound is tight up to an additive factor.<br />Full version of the paper to be presented in CALDAM 2020
- Subjects :
- FOS: Computer and information sciences
Star network
Discrete Mathematics (cs.DM)
0211 other engineering and technologies
0102 computer and information sciences
02 engineering and technology
Orientation (graph theory)
Star (graph theory)
05C20, 05C12
Network topology
01 natural sciences
Upper and lower bounds
Prime (order theory)
Combinatorics
Permutation
FOS: Mathematics
Mathematics - Combinatorics
Discrete Mathematics and Combinatorics
Mathematics
Applied Mathematics
021107 urban & regional planning
Computer Science - Distributed, Parallel, and Cluster Computing
010201 computation theory & mathematics
Distributed, Parallel, and Cluster Computing (cs.DC)
Combinatorics (math.CO)
Hypercube
Computer Science - Discrete Mathematics
Subjects
Details
- ISSN :
- 0166218X
- Volume :
- 319
- Database :
- OpenAIRE
- Journal :
- Discrete Applied Mathematics
- Accession number :
- edsair.doi.dedup.....b23159fbea48905810b8ab075328b57c