Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
A Forward-Backward Single-Source Shortest Paths Algorithm - MaRDI portal

A Forward-Backward Single-Source Shortest Paths Algorithm (Q5255013)

From MaRDI portal

Jump to:navigation, search

scientific article; zbMATH DE number 6445034

Language	Label	Description	Also known as
English	A Forward-Backward Single-Source Shortest Paths Algorithm	scientific article; zbMATH DE number 6445034

Statements

scholarly article

0 references

A Forward-Backward Single-Source Shortest Paths Algorithm (English)

0 references

0 references

David Bruce Wilson

0 references

SIAM Journal on Computing

0 references

publication date

11 June 2015

0 references

full work available at URL

https://arxiv.org/abs/1405.7619

0 references

zbMATH Keywords

shortest paths

0 references

random graphs

0 references

average case analysis

0 references

MaRDI profile type

MaRDI publication profile

0 references

Faster algorithms for the shortest path problem

0 references

Weak disorder asymptotics in the stochastic mean-field model of distance

0 references

A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$

0 references

Time bounds for selection

0 references

Buckets, Heaps, Lists, and Monotone Priority Queues

0 references

0 references

On the Shortest Route Through a Network

0 references

The expected length of a shortest path

0 references

A new approach to dynamic all pairs shortest paths

0 references

Experimental analysis of dynamic all pairs shortest path algorithms

0 references

A note on two problems in connexion with graphs

0 references

Correlation inequalities on some partially ordered sets

0 references

Fibonacci heaps and their uses in improved network optimization algorithms

0 references

The shortest-path problem for graphs with random arc-lengths

0 references

A Practical Shortest Path Algorithm with Linear Expected Time

0 references

Simpler computation of single-source shortest paths in linear average time

0 references

On Shortest Paths in Graphs with Random Weights

0 references

One, Two and Three Times log <i>n</i>/<i>n</i> for Paths in a Complete Graph with Random Weights

0 references

A bidirectional shortest-path algorithm with good average-case behavior

0 references

0 references

Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds

0 references

An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$

0 references

Finding the Shortest Route between Two Points in a Network

0 references

All-Pairs Shortest Paths in $O(n^2)$ time with high probability

0 references

A new approach to all-pairs shortest paths on real-weighted graphs

0 references

0 references

A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average Time $O(n^2 \log ^2 n)$

0 references

A simplified algorithm for the all pairs shortest path problem with \(O(n ^{2} \log n)\) expected time

0 references

A Simpler Algorithm for the All Pairs Shortest Path Problem with O(n 2logn) Expected Time

0 references

0 references

Undirected single-source shortest paths with positive integer weights in linear time

0 references

Equivalence between priority queues and sorting

0 references

Probability with Martingales

0 references

Identifiers

zbMATH Open document ID

0 references

10.1137/140970975

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

zbMATH DE Number

0 references

0 references

0 references

0 references

DBLP publication ID

journals/siamcomp/WilsonZ15

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5255013

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q5255013&oldid=39802755"