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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We present new deterministic algorithms for computing distributed weightedminimum weight cycle (MWC) in undirected and directed graphs and distributedweighted all nodes shortest cycle (ANSC) in directed graphs. Our algorithms forthese problems run in $\tilde{O}(n)$ rounds in the CONGEST model on graphs witharbitrary non-negative edge weights, matching the lower bound up topolylogarithmic factors. Before our work, no near linear rounds deterministicalgorithms were known for these problems. The previous best bound for solvingthese problems deterministically requires an initial computation of all pairsshortest paths (APSP) on the given graph, followed by post-processing of $O(n)$rounds, and in total takes $\tilde{O}(n^{4/3})$ rounds, using deterministicAPSP~\cite{AR-SPAA20}.  The main component of our new $\tilde{O}(n)$ rounds algorithms is adeterministic technique for constructing a sequence of successive blocker sets.These blocker sets are then treated as source nodes to compute $h$-hop shortestpaths, which can then be used to compute candidate shortest cycles whose hoplength lies in a particular range. The shortest cycles can then be obtained byselecting the cycle with the minimum weight from all these candidate cycles.  Additionally using the above blocker set sequence technique, we also obtain$\tilde{O}(n)$ rounds deterministic algorithm for the multi-source shortestpaths problem (MSSP) for both directed and undirected graphs, given that thesize of the source set is at most $\sqrt{n}$. This new result for MSSP can be astep towards obtaining a $o(n^{4/3})$ rounds algorithm for deterministic APSP.We also believe that our new blocker set sequence technique may have potentialapplications for other distributed algorithms.

Distributed Deterministic Exact Minimum Weight Cycle and Multi Source Shortest Paths in Near Linear Rounds in CONGEST model