The Experts below are selected from a list of 39102 Experts worldwide ranked by ideXlab platform
Uri Zwick - One of the best experts on this subject based on the ideXlab platform.
-
a forward backward single source shortest paths algorithm
SIAM Journal on Computing, 2015Co-Authors: David B. Wilson, Uri ZwickAbstract:We describe a new forward-backward variant of Dijkstra's and Spira's single-source shortest paths (SSSP) algorithms. While essentially all SSSP algorithms scan edges only forward, the new algorithm scans some edges backward. The new algorithm assumes that edges in the outgoing and incoming adjacency lists of the vertices appear in nondecreasing order of weight. (Spira's algorithm makes the same assumption about the outgoing adjacency lists but does not use incoming adjacency lists.) The running time of the algorithm on a complete directed graph on $n$ vertices with Independent Exponential edge weights is $O(n)$ with very high probability. This improves on the previous best result of $O(n\log n)$, which is best possible if only forward scans are allowed, exhibiting an interesting separation between forward-only and forward-backward SSSP algorithms. As a consequence, we also get a new all-pairs shortest paths algorithm. The expected running time of the algorithm on complete graphs with Independent exponenti...
-
a forward backward single source shortest paths algorithm
arXiv: Data Structures and Algorithms, 2014Co-Authors: David B. Wilson, Uri ZwickAbstract:We describe a new forward-backward variant of Dijkstra's and Spira's Single-Source Shortest Paths (SSSP) algorithms. While essentially all SSSP algorithm only scan edges forward, the new algorithm scans some edges backward. The new algorithm assumes that edges in the outgoing and incoming adjacency lists of the vertices appear in non-decreasing order of weight. (Spira's algorithm makes the same assumption about the outgoing adjacency lists, but does not use incoming adjacency lists.) The running time of the algorithm on a complete directed graph on $n$ vertices with Independent Exponential edge weights is $O(n)$, with very high probability. This improves on the previously best result of $O(n\log n)$, which is best possible if only forward scans are allowed, exhibiting an interesting separation between forward-only and forward-backward SSSP algorithms. As a consequence, we also get a new all-pairs shortest paths algorithm. The expected running time of the algorithm on complete graphs with Independent Exponential edge weights is $O(n^2)$, matching a recent algorithm of Demetrescu and Italiano as analyzed by Peres et al. Furthermore, the probability that the new algorithm requires more than $O(n^2)$ time is Exponentially small, improving on the $O(n^{-1/26})$ probability bound obtained by Peres et al.
-
A Forward-Backward Single-Source Shortest Paths Algorithm
2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 2013Co-Authors: David B. Wilson, Uri ZwickAbstract:We describe a new forward-backward variant of Dijkstra's and Spira's Single-Source Shortest Paths (SSSP) algorithms. While essentially all SSSP algorithm only scan edges forward, the new algorithm scans some edges backward. The new algorithm assumes that edges in the out-going and incoming adjacency lists of the vertices appear in nondecreasing order of weight. (Spira's algorithm makes the same assumption about the out-going adjacency lists, but does not use incoming adjacency lists.) The running time of the algorithm on a complete directed graph on n vertices with Independent Exponential edge weights is O(n), with very high probability. This improves on the previously best result of O(n log n), which is best possible if only forward scans are allowed, exhibiting an interesting separation between forward-only and forward-backward SSSP algorithms. As a consequence, we also get a new all-pairs shortest paths algorithm. The expected running time of the algorithm on complete graphs with Independent Exponential edge weights is O(n2), matching a recent result of Peres et al. Furthermore, the probability that the new algorithm requires more than O(n2) time is Exponentially small, improving on the polynomially small probability of Peres et al.
David B. Wilson - One of the best experts on this subject based on the ideXlab platform.
-
a forward backward single source shortest paths algorithm
SIAM Journal on Computing, 2015Co-Authors: David B. Wilson, Uri ZwickAbstract:We describe a new forward-backward variant of Dijkstra's and Spira's single-source shortest paths (SSSP) algorithms. While essentially all SSSP algorithms scan edges only forward, the new algorithm scans some edges backward. The new algorithm assumes that edges in the outgoing and incoming adjacency lists of the vertices appear in nondecreasing order of weight. (Spira's algorithm makes the same assumption about the outgoing adjacency lists but does not use incoming adjacency lists.) The running time of the algorithm on a complete directed graph on $n$ vertices with Independent Exponential edge weights is $O(n)$ with very high probability. This improves on the previous best result of $O(n\log n)$, which is best possible if only forward scans are allowed, exhibiting an interesting separation between forward-only and forward-backward SSSP algorithms. As a consequence, we also get a new all-pairs shortest paths algorithm. The expected running time of the algorithm on complete graphs with Independent exponenti...
-
a forward backward single source shortest paths algorithm
arXiv: Data Structures and Algorithms, 2014Co-Authors: David B. Wilson, Uri ZwickAbstract:We describe a new forward-backward variant of Dijkstra's and Spira's Single-Source Shortest Paths (SSSP) algorithms. While essentially all SSSP algorithm only scan edges forward, the new algorithm scans some edges backward. The new algorithm assumes that edges in the outgoing and incoming adjacency lists of the vertices appear in non-decreasing order of weight. (Spira's algorithm makes the same assumption about the outgoing adjacency lists, but does not use incoming adjacency lists.) The running time of the algorithm on a complete directed graph on $n$ vertices with Independent Exponential edge weights is $O(n)$, with very high probability. This improves on the previously best result of $O(n\log n)$, which is best possible if only forward scans are allowed, exhibiting an interesting separation between forward-only and forward-backward SSSP algorithms. As a consequence, we also get a new all-pairs shortest paths algorithm. The expected running time of the algorithm on complete graphs with Independent Exponential edge weights is $O(n^2)$, matching a recent algorithm of Demetrescu and Italiano as analyzed by Peres et al. Furthermore, the probability that the new algorithm requires more than $O(n^2)$ time is Exponentially small, improving on the $O(n^{-1/26})$ probability bound obtained by Peres et al.
-
A Forward-Backward Single-Source Shortest Paths Algorithm
2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 2013Co-Authors: David B. Wilson, Uri ZwickAbstract:We describe a new forward-backward variant of Dijkstra's and Spira's Single-Source Shortest Paths (SSSP) algorithms. While essentially all SSSP algorithm only scan edges forward, the new algorithm scans some edges backward. The new algorithm assumes that edges in the out-going and incoming adjacency lists of the vertices appear in nondecreasing order of weight. (Spira's algorithm makes the same assumption about the out-going adjacency lists, but does not use incoming adjacency lists.) The running time of the algorithm on a complete directed graph on n vertices with Independent Exponential edge weights is O(n), with very high probability. This improves on the previously best result of O(n log n), which is best possible if only forward scans are allowed, exhibiting an interesting separation between forward-only and forward-backward SSSP algorithms. As a consequence, we also get a new all-pairs shortest paths algorithm. The expected running time of the algorithm on complete graphs with Independent Exponential edge weights is O(n2), matching a recent result of Peres et al. Furthermore, the probability that the new algorithm requires more than O(n2) time is Exponentially small, improving on the polynomially small probability of Peres et al.
Mohamedslim Alouini - One of the best experts on this subject based on the ideXlab platform.
-
end to end performance of transmission systems with relays over rayleigh fading channels
IEEE Transactions on Wireless Communications, 2003Co-Authors: Mazen O Hasna, Mohamedslim AlouiniAbstract:End-to-end performance of two-hop wireless communication systems with nonregenerative relays over flat Rayleigh-fading channels is presented. This is accomplished by deriving and applying some new closed-form expressions for the statistics of the harmonic mean of two Independent Exponential variates. It is shown that the presented results can either be exact or tight lower bounds on the performance of these systems depending on the choice of the relay gain. More specifically, average bit-error rate expressions for binary differential phase-shift keying, as well as outage probability formulas for noise limited systems are derived. Finally, comparisons between regenerative and nonregenerative systems are presented. Numerical results show that the former systems clearly outperform the latter ones for low average signal-to-noise-ratio (SNR). They also show that the two systems have similar performance at high average SNR.
-
performance analysis of two hop relayed transmissions over rayleigh fading channels
Vehicular Technology Conference, 2002Co-Authors: Mazen O Hasna, Mohamedslim AlouiniAbstract:Closed form expressions for the statistics of the harmonic mean of two Independent Exponential variates are presented. These statistical results are then applied to study the performance of wireless communication systems with non-regenerative relays over flat Rayleigh fading channels. It is shown that these results can either be exact or tight lower bounds on the performance of these systems depending on the choice of the relay gain. More specifically, outage probability formulas for noise limited systems are obtained. Furthermore, outage capacity and bit error rate (BER) expressions for binary differential phase shift keying are derived. Finally, comparisons between regenerative and non-regenerative systems are presented. Numerical results show that the former systems clearly outperform the latter ones for low average signal-to-noise-ratio (SNR). They also show that the two systems have similar performance at high average SNR.
Michael L. Ulrey - One of the best experts on this subject based on the ideXlab platform.
-
Formulas for the distribution of sums of Independent Exponential random variables
IEEE Transactions on Reliability, 2003Co-Authors: Michael L. UlreyAbstract:This paper derives a new type of formula for the probability that, among a collection of items with s-Independent Exponential times to failure, a certain subset of them fails in a given order before a certain time, and all the remaining items survive beyond that time. This formula is in the form of a power series that satisfies a certain constant coefficient linear differential equation with specified initial conditions. This provides an alternative to existing closed-form formulas of the "exponomial" variety, viz., a nonlinear combination of Exponential terms, where the coefficients of the Exponential terms are polynomials in the mission time. Some results are given which quantify the computation effort required to achieve a specified accuracy using partial sums of the infinite series; a simple example illustrates these results. This approach can be very efficient for system reliability analysis where the product of the mission time and the sum of the failure rates down any path leading to system failure is small. Further work is needed to expand the practical applicability of this approach to cases where some rates are large and/or the mission time is long.
Gerard Hooghiemstra - One of the best experts on this subject based on the ideXlab platform.
-
Extreme value theory, Poisson-Dirichlet distributions, and first passage percolation on random networks
2020Co-Authors: Shankar Bhamidi, Remco Van Der Hofstad, Gerard HooghiemstraAbstract:Abstract We study first passage percolation on the configuration model (CM) having power-law degrees with exponent τ ∈ [1, 2). To this end we equip the edges with Exponential weights. We derive the distributional limit of the minimal weight of a path between typical vertices in the network and the number of edges on the minimal weight path, which can be computed in terms of the Poisson-Dirichlet distribution. We explicitly describe these limits via the construction of an infinite limiting object describing the FPP problem in the densely connected core of the network. We consider two separate cases, namely, the original CM, in which each edge, regardless of its multiplicity, receives an Independent Exponential weight, as well as the erased CM, for which there is an Independent Exponential weight between any pair of direct neighbors. While the results are qualitatively similar, surprisingly the limiting random variables are quite different. Our results imply that the flow carrying properties of the network are markedly different from either the mean-field setting or the locally tree-like setting, which occurs as τ > 2, and for which the hopcount between typical vertices scales as log n. In our setting the hopcount is tight and has an explicit limiting distribution, showing that one can transfer information remarkably quickly between different vertices in the network. This efficiency has a down side in that such networks are remarkably fragile to directed attacks. These results continue a general program by the authors to obtain a complete picture of how random disorder changes the inherent geometry of various random network models, se
-
extreme value theory poisson dirichlet distributions and first passage percolation on random networks
Advances in Applied Probability, 2010Co-Authors: Shankar Bhamidi, Remco Van Der Hofstad, Gerard HooghiemstraAbstract:We study first passage percolation (FPP) on the configuration model (CM) having power-law degrees with exponent ? ? [1, 2) and Exponential edge weights. We derive the distributional limit of the minimal weight of a path between typical vertices in the network and the number of edges on the minimal-weight path, both of which can be computed in terms of the Poisson-Dirichlet distribution. We explicitly describe these limits via construction of infinite limiting objects describing the FPP problem in the densely connected core of the network. We consider two separate cases, the original CM, in which each edge, regardless of its multiplicity, receives an Independent Exponential weight, and the erased CM, for which there is an Independent Exponential weight between any pair of direct neighbors. While the results are qualitatively similar, surprisingly, the limiting random variables are quite different. Our results imply that the flow carrying properties of the network are markedly different from either the mean-field setting or the locally tree-like setting, which occurs as ? > 2, and for which the hopcount between typical vertices scales as log n. In our setting the hopcount is tight and has an explicit limiting distribution, showing that information can be transferred remarkably quickly between different vertices in the network. This efficiency has a down side in that such networks are remarkably fragile to directed attacks. These results continue a general program by the authors to obtain a complete picture of how random disorder changes the inherent geometry of various random network models; see Aldous and Bhamidi (2010), Bhamidi (2008), and Bhamidi, van der Hofstad and Hooghiemstra (2009).
