English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A common technique to speed up shortest path queries in graphs is to use abidirectional search, i.e., performing a forward search from the start and abackward search from the destination until a common vertex on a shortest pathis found. In practice, this has a tremendous impact on the performance on somereal-world networks, while it only seems to save a constant factor on othertypes of networks. Even though finding shortest paths is a ubiquitous problem,there are only few studies attempting to understand the apparently asymptoticspeedups on some networks, using average case analysis on certain models forreal-world networks.  In this paper we give a new perspective on this, by analyzing deterministicproperties that permit theoretical analysis and that can easily be checked onany particular instance. We prove that these parameters imply sublinear runningtime for the bidirectional breadth-first search in several regimes, some ofwhich are tight. Moreover, we perform experiments on a large set of real-worldnetworks showing that our parameters capture the concept of practical runningtime well.

Deterministic Performance Guarantees for Bidirectional BFS on Real-World Networks