The Experts below are selected from a list of 76770 Experts worldwide ranked by ideXlab platform
Ash Mohammad Abbas - One of the best experts on this subject based on the ideXlab platform.
-
Analysis of Multiple Attempt Multipath Routing for mobile ad hoc networks
International Journal of Ad Hoc and Ubiquitous Computing, 2010Co-Authors: Ash Mohammad AbbasAbstract:In this paper, we analyse a routing protocol that identifies a Maximal Set of node-disjoint paths between a given source and a destination in multiple attempts using an approach that is a combination of a single-go routing protocol and an incremental protocol. We prove that doing so preserves the guarantee inherited from the incremental protocol to discover a Maximal Set of node-disjoint paths. In our analysis, we focus on the computational and communication overheads incurred in identifying node-disjoint paths and the time after which all routes identified are expected to fail.
-
A Hybrid Protocol for Identification of a Maximal Set of Node Disjoint Paths in Mobile Ad hoc Networks
The International Arab Journal of Information Technology, 2009Co-Authors: Ash Mohammad AbbasAbstract:Identifying a Maximal Set of node-disjoint paths between a given source and a destination is a challenging task in mobile ad hoc networks. One cannot guarantee to identify the Maximal Set of node-disjoint paths in a single sequence of request-reply cycle. However, one can guarantee to identify a Maximal Set of node-disjoint paths in an incremental fashion using multiple route discoveries. In this paper, we present a protocol that adopts an approach that is a hybrid of the approaches taken by a protocol that tries to identify multiple node-disjoint paths in a single go and a protocol that identifies them incrementally. Our approach preserves the guarantee to discover a Maximal Set of node-disjoint paths between a given source and a destination. Further, we have shown that our approach is scalable and it requires less number of route discoveries than that required by an incremental protocol.
-
ICON - Analysis of a hybrid protocol for identification of a Maximal Set of node-disjoint paths in mobile Ad hoc networks
2008 16th IEEE International Conference on Networks, 2008Co-Authors: Ash Mohammad AbbasAbstract:In this paper, we analyze a protocol that is hybrid of an incremental protocol and a protocol that tries to identify multiple node-disjoint paths in a single route discovery. We prove that the hybrid protocol preserves the guarantee inherited from the incremental protocol about the identification of a Maximal Set of node-disjoint paths. In our analysis, we focus on the following parameters: (i) communication and computational overheads, and (ii) route failure time.
-
COMSWARE - An Improvement over Incremental Approach for Guaranteed Identification of Multiple Node-Disjoint Paths in Mobile Ad hoc Networks
2007 2nd International Conference on Communication Systems Software and Middleware, 2007Co-Authors: Ash Mohammad Abbas, Tehzeeb Ahmed AbbasiAbstract:Identifying a Maximal Set of node-disjoint paths between a given source and a destination is a challenging task in mobile ad hoc networks. One cannot guarantee to identify the Maximal Set of node-disjoint paths in a single sequence of request-reply cycle. However, one can guarantee to identify the Maximal Set of node-disjoint paths in multiple attempts and in an incremental fashion. One may combine a protocol that tries to identify multiple node-disjoint paths in a single go with an incremental approach. In this paper, we present an improved version of an incremental protocol that is guaranteed to discover the Maximal Set of node-disjoint paths between a given source and a destination. We have analytically shown that our approach requires less number of route discoveries than that required by the existing incremental protocol. We have also discussed the scalability of the proposed approach.
Lars Ehlers - One of the best experts on this subject based on the ideXlab platform.
-
Von Neumann-Morgenstern stable Sets in matching problems
Journal of Economic Theory, 2007Co-Authors: Lars EhlersAbstract:The following properties of the core of a one well-known: (i) the core is non-empty; (ii) the core is a lattice; and (iii) the Set of unmatched agents is identical for any two matchings belonging to the core. The literature on two-sided matching focuses almost exclusively on the core and studies extensively its properties. Our main result is the following characterization of (von Neumann-Morgenstern) stable Sets in one-to-one matching problem only if it is a Maximal Set satisfying the following properties : (a) the core is a subSet of the Set; (b) the Set is a lattice; (c) the Set of unmatched agents is identical for any two matchings belonging to the Set. Furthermore, a Set is a stable Set if it is the unique Maximal Set satisfying properties (a), (b) and (c). We also show that our main result does not extend from one-to-one matching problems to many-to-one matching problems.(This abstract was borrowed from another version of this item.)
-
Von Neumann-Morgenstern Stable Sets in Matching Problems
2005Co-Authors: Lars EhlersAbstract:The following properties of the core of a one well-known: (i) the core is non-empty; (ii) the core is a lattice; and (iii) the Set of unmatched agents is identical for any two matchings belonging to the core. The literature on two-sided matching focuses almost exclusively on the core and studies extensively its properties. Our main result is the following characterization of (von Neumann-Morgenstern) stable Sets in one-to-one matching problem only if it is a Maximal Set satisfying the following properties : (a) the core is a subSet of the Set; (b) the Set is a lattice; (c) the Set of unmatched agents is identical for any two matchings belonging to the Set. Furthermore, a Set is a stable Set if it is the unique Maximal Set satisfying properties (a), (b) and (c). We also show that our main result does not extend from one-to-one matching problems to many-to-one matching problems.
-
von neumann morgenstern stable Sets in matching problems
Cahiers de recherche, 2005Co-Authors: Lars EhlersAbstract:The following properties of the core of a one-to-one matching problem are well-known: (i) the core is non-empty; (ii) the core is a lattice; and (iii) the Set of unmatched agents is identical for any two matchings belonging to the core. The literature on two-sided matching focuses almost exclusively on the core and studies extensively its properties. Our main result is the following characterization of (von Neumann-Morgenstern) stable Sets in one-to-one matching problems. We show that a Set of matchings is a stable Set of a one-to-one matching problem only if it is a Maximal Set satisfying the following properties: (a) the core is a subSet of the Set; (b) the Set is a lattice; and (c) the Set of unmatched agents is identical for any two matchings belonging to the Set. Furthermore, a Set is a stable Set if it is the unique Maximal Set satisfying properties (a), (b), and (c). We also show that our main result does not extend from one-to-one matching problems to many-to-one matching problems.
Kunal Sengupta - One of the best experts on this subject based on the ideXlab platform.
-
rational choice and von neumann morgenstern s stable Set the case of path dependent procedures
Social Choice and Welfare, 2006Co-Authors: Taradas Bandyopadhyay, Kunal SenguptaAbstract:Describing a procedure in which choice proceeds in a sequence, we propose two alternative ways of resolving the decision problem whenever the outcome is sequence sensitive. One way yields a rationalizable choice Set, and the other way produces a weakly rationalizable choice Set that is equivalent to von Neumann–Morgenstern’s stable Set. It is shown that for quasi-transitive rationalization, the Maximal Set must coincide with its stable Set.
Alok Aggarwal - One of the best experts on this subject based on the ideXlab platform.
-
Parallel complexity of computing a Maximal Set of disjoint paths
Information Processing Letters, 1992Co-Authors: Alok AggarwalAbstract:Abstract Given a graph, G = (V, E), and Sets S ⊂ V and Q ⊂ V, the Maximal paths problem requires the computation of a Maximal Set of vertex disjoint paths in G that begin at vertices of S and end at vertices of Q. It is well known that this problem can be solved sequentially in time that is proportional to the number of edges in G. However, its parallel complexity is not known. This note shows that this problem is NC-reducible to that of computing a depth-first search forest in a suitable n-vertex graph. This result can also be extended to directed graphs.
Zhi-zhong Chen - One of the best experts on this subject based on the ideXlab platform.
-
COCOON - Fast RNC and NC Algorithms for Finding a Maximal Set of Paths with an Application
Lecture Notes in Computer Science, 1996Co-Authors: Ryuhei Uehara, Zhi-zhong ChenAbstract:We present two parallel algorithms for finding a Maximal Set of paths in a given undirected graph. The former runs in O(log n) expected time with O(n + m) processors on a CRCW PRAM. The latter runs in O(log2n) time with O(Δ2(n + m)/log n) processors on an EREW PRAM. The results improve on the best previous ones and can also be extended to digraphs. We then use the results to design an NC approximation algorithm for a variation of the shortest superstring problem introduced by Jiang et al. The approximation algorithm achieves a compression ratio of \(\frac{1}{{3 + \varepsilon }}\)for any e >0.
-
ICALP - NC Algorithms for Finding a Maximal Set of Paths with Application to Compressing Strings
Automata Languages and Programming, 1995Co-Authors: Zhi-zhong ChenAbstract:It is shown that the problem of finding a Maximal Set of paths in a given (undirected or directed) graph is in NC. This result is then used to obtain three parallel approximation algorithms for the shortest superstring problem. The first is an NC algorithm achieving a compression ratio of 1/3+e for any e > 0. The second is an RNC algorithm achieving a compression ratio of 38/63 ≈ 0.603. The third is an RNC algorithm achieving an approximation ratio of 2 50/63 ≈ 2.793. All the results significantly improve on the best previous ones.
