Name
Abstract | ||
|---|---|---|
We investigate the problem of constructing the maximal number of node disjoint paths between two distinct nodes in Swapped/OTIS networks. A general construction of node disjoint paths in any OTIS network with a connected basis network is presented, which is independent of any construction of node disjoint paths in its basis network. This general construction is effective and efficient, which can obtain desirable node disjoint paths of length at most D+4 in O(Δ2+Δf(N1/2)) time if the basis network of size n has a shortest routing algorithm of time complexity O(f(n)), where D, Δ and N are, respectively, the diameter, the degree and the size of the OTIS network. Further, for OTIS networks with maximally fault tolerant basis networks, we give an improved version of a conventional construction of node disjoint paths by incorporating the above general construction. Finally, we show the effectiveness and efficiency of these constructions applied to OTIS-Hypercubes. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-76837-1_22 | APPT |
Keywords | Field | DocType |
general construction,distinct node,conventional construction,basis network,maximally fault tolerant basis,size n,efficient construction,node disjoint path,desirable node disjoint path,connected basis network,otis network,fault tolerant,time complexity | Discrete mathematics,Disjoint sets,Computer science,Algorithm,Fault tolerance,Disjoint path,Time complexity,Routing algorithm | Conference |
Volume | ISSN | ISBN |
4847 | 0302-9743 | 3-540-76836-X |
Citations | PageRank | References |
2 | 0.37 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Weidong Chen | 1 | 40 | 4.62 |
| Wenjun Xiao | 2 | 218 | 25.54 |
| Behrooz Parhami | 3 | 687 | 104.30 |