✦ LIBER ✦

The bit-operation complexity of matrix multiplication and of all pair shortest path problem

✍ Scribed by V.Ya. Pan

Publisher: Elsevier Science
Year: 1981
Tongue: English
Weight: 623 KB
Volume: 7
Category: Article
ISSN: 0898-1221
DOI: 10.1016/0898-1221(81)90130-9

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the Exponent of the All Pairs Shortes

On the Exponent of the All Pairs Shortest Path Problem

✍ Noga Alon; Zvi Galil; Oded Margalit 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 900 KB

The upper bound on the exponent, |, of matrix multiplication over a ring that was three in 1968 has decreased several times and since 1986 it has been 2.376. On the other hand, the exponent of the algorithms known for the all pairs shortest path problem has stayed at three all these years even for t

The time-dependent shortest pair of disj

The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms

✍ Sherali, Hanif D.; Ozbay, Kaan; Subramanian, Shivaram 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 160 KB 👁 3 views

In this paper, we examine complexity issues, models, and algorithms for the problem of finding a shortest pair of disjoint paths between two nodes of a network such that the total travel delay is minimized, given that the individual arc delays are time-dependent. Such disjoint paths address the issu

On the all-pairs shortest-path algorithm

On the all-pairs shortest-path algorithm of Moffat and Takaoka

✍ Kurt Mehlhorn; Volker Priebe 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 3 views

We review how to solve the all-pairs shortest-path problem in a nonnegatively Ž 2 . weighted digraph with n vertices in expected time O n log n . This bound is shown to hold with high probability for a wide class of probability distributions on nonnegatively weighted Ž . digraphs. We also prove that

A sharper analysis of a parallel algorit

A sharper analysis of a parallel algorithm for the all pairs shortest path problem

✍ Qian Ping Gu; Tadao Takaoka 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 457 KB

A mean-time comparison of algorithms for

A mean-time comparison of algorithms for the all-pairs shortest-path problem with arbitrary arc lengths

✍ W. D. Kelton; A. M. Law 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 522 KB

The bit complexity of matrix multiplicat

The bit complexity of matrix multiplication and of related computations in linear algebra. The segmented λ algorithms

✍ V.Y. Pan 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 869 KB

The numbers of bit operations (br) required for matrix multiplication (MM), matrix inversion (MI). the evaluation of the determinant of a matrix (Det). and the solution of a system of linear equations (SLE) are estimated from above and below. (For SLE the estimates are nearly sharp.) The bit-complex