Loading...
Please wait, while we are loading the content...
Similar Documents
Efficient algorithms for Disjoint Paths in Hypercubes and Star Networks
| Content Provider | Semantic Scholar |
|---|---|
| Author | Okawa, Satoshi Peng, Shietung |
| Copyright Year | 1994 |
| Abstract | Recently, graph parameters such as the number of disjoint paths between a pair of nodes (or between a node and a set of nodes and so on) and the length of these paths have been studied extensively due to their relations to (applications in) fault tolerance and transmission delay in communication networks. We give efficient algorithms for node disjoint path problems in hypercubes, star graphs, and incomplete star graphs which are defined to reduce the large gaps in the size of systems based on star graph topologies. Four disjoint path paradigms are discussed: (1) disjoint paths between a pair of nodes $s$ and $t,$ (2) disjoint paths from a node $s$ to a set $T$ of nodes, (3) disjoint paths from a set $S$ of nodes to a set $T$ of nodes, and (4) disjoint paths between node pairs $(s_{i}, t_{i}),$ $1\leq i\leq k$ . We give algorithms for paradigms (3) and (4) in hypercubes and algorithms for all the paradigms in star graphs and incomplete star graphs. Our algorithms can find the maximum number of disjoint paths for these paradigms in optimal time. For an n-dimensional hypercube $H_{n}$ , the length of the disjoint paths given by our algorithms is at most $2d(H.)-2=2n-2$ , where $d(G)$ is the diameter of the graph $G$ . Fer an n-dimensional star graph $G_{n}$ and an incomplete star graph $G_{n,m}$ , the length of the disjoint paths constructed by our algorithms is at most $d(G.)+c$ and $d(G_{n,m})+c$, respectively, where $c$ is a small constant. Introduction In the design and implementation of a large multiprocessor system, one of the key and most fundamental issues is the design of the interconnection network through which the processors can communicate efficiently. Taking the cost, reliability, fault tolerance, and transmission delay into consideration, a good interconnection network should be a sparse and homogeneous graph with connectivity as large as possible and diameter as small as possible. With the development of VLSI and fiber optics technologies, the size of multiprocessor system is increasing tremendously. The fault tolerance communication has become one of the central issues in today’s multiprocessors system. Recently, some new parameters (will be given in the next section) which concerns a collection of disjoint paths (in this paper, disjoint path refers node disjoint path unless otherwisw mentioned) between a pair of nodes (or between a node and a set of nodes, and so on) have been introduced to evaluate the fault tolerance properties of interconnection networks $[10, 18]$ . Much work has been done on finding the disjoint paths in general graphs as well as some special classes of interconnection networks [10, 9, 18, 4, 13]. In this paper, disjoint paths problems in hypercube, star graph, and incomplete star graph interconnection networks are considered. 数理解析研究所講究録 第 871巻 1994年 105-111 |
| Starting Page | 105 |
| Ending Page | 111 |
| Page Count | 7 |
| File Format | PDF HTM / HTML |
| Volume Number | 871 |
| Alternate Webpage(s) | https://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/84049/1/0871-17.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
