𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the cardinality of the Pareto set in bicriteria shortest path problems

✍ Scribed by Matthias Müller-Hannemann; Karsten Weihe

Publisher
Springer US
Year
2006
Tongue
English
Weight
509 KB
Volume
147
Category
Article
ISSN
0254-5330

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

On the All-Pairs-Shortest-Path Problem i
On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs
✍ R. Seidel 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 318 KB

We present an algorithm, APD, that solves the distance version of the all-pairs-shortest-path problem for undirected, unweighted \(n\)-vertex graphs in time \(O(M(n) \log n)\), where \(M(n)\) denotes the time necessary to multiply two \(n \times n\) matrices of small integers (which is currently kno