Abstract: Qk
n has been shown as an alternative to the hypercube
family. For any even integer k ≥ 4 and any integer n ≥ 2, Qk
n is
a bipartite graph. In this paper, we will prove that given any pair of
vertices, w and b, from different partite sets of Qk
n, there exist 2n
internally disjoint paths between w and b, denoted by {Pi | 0 ≤ i ≤ 2n-1}, such that 2n-1
i=0 Pi covers all vertices of Qk
n. The result is
optimal since each vertex of Qk
n has exactly 2n neighbors.
Abstract: Topological changes in mobile ad hoc networks
frequently render routing paths unusable. Such recurrent path failures
have detrimental effects on quality of service. A suitable technique
for eliminating this problem is to use multiple backup paths between
the source and the destination in the network. This paper proposes an
effective and efficient protocol for backup and disjoint path set in ad
hoc wireless network. This protocol converges to a highly reliable
path set very fast with no message exchange overhead. The paths
selection according to this algorithm is beneficial for mobile ad hoc
networks, since it produce a set of backup paths with more high
reliability. Simulation experiments are conducted to evaluate the
performance of our algorithm in terms of route numbers in the path
set and its reliability. In order to acquire link reliability estimates, we
use link expiration time (LET) between two nodes.
Abstract: In practice, wireless networks has the property that
the signal strength attenuates with respect to the distance from the
base station, it could be better if the nodes at two hop away are
considered for better quality of service. In this paper, we propose a
procedure to identify delay preserving substructures for a given
wireless ad-hoc network using a new graph operation G 2 – E (G) =
G* (Edge difference of square graph of a given graph and the
original graph). This operation helps to analyze some induced
substructures, which preserve delay in communication among them.
This operation G* on a given graph will induce a graph, in which 1-
hop neighbors of any node are at 2-hop distance in the original
network. In this paper, we also identify some delay preserving
substructures in G*, which are (i) set of all nodes, which are mutually
at 2-hop distance in G that will form a clique in G*, (ii) set of nodes
which forms an odd cycle C2k+1 in G, will form an odd cycle in G*
and the set of nodes which form a even cycle C2k in G that will form
two disjoint companion cycles ( of same parity odd/even) of length k
in G*, (iii) every path of length 2k+1 or 2k in G will induce two
disjoint paths of length k in G*, and (iv) set of nodes in G*, which
induces a maximal connected sub graph with radius 1 (which
identifies a substructure with radius equal 2 and diameter at most 4 in
G). The above delay preserving sub structures will behave as good
clusters in the original network.