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

Amiri and Wargalla (2020) proved the following local-to-global theorem indirected acyclic graphs (DAGs): if $G$ is a weighted DAG such that for eachsubset $S$ of 3 nodes there is a shortest path containing every node in $S$,then there exists a pair $(s,t)$ of nodes such that there is a shortest$st$-path containing every node in $G$.  We extend this theorem to general graphs. For undirected graphs, we provethat the same theorem holds (up to a difference in the constant 3). Fordirected graphs, we provide a counterexample to the theorem (for any constant),and prove a roundtrip analogue of the theorem which shows there exists a pair$(s,t)$ of nodes such that every node in $G$ is contained in the union of ashortest $st$-path and a shortest $ts$-path.  The original theorem for DAGs has an application to the $k$-Shortest Pathswith Congestion $c$ (($k,c$)-SPC) problem. In this problem, we are given aweighted graph $G$, together with $k$ node pairs $(s_1,t_1),\dots,(s_k,t_k)$,and a positive integer $c\leq k$. We are tasked with finding paths $P_1,\dots,P_k$ such that each $P_i$ is a shortest path from $s_i$ to $t_i$, and everynode in the graph is on at most $c$ paths $P_i$, or reporting that no suchcollection of paths exists.  When $c=k$ the problem is easily solved by finding shortest paths for eachpair $(s_i,t_i)$ independently. When $c=1$, the $(k,c)$-SPC problem recoversthe $k$-Disjoint Shortest Paths ($k$-DSP) problem, where the collection ofshortest paths must be node-disjoint. For fixed $k$, $k$-DSP can be solved inpolynomial time on DAGs and undirected graphs. Previous work shows that thelocal-to-global theorem for DAGs implies that $(k,c)$-SPC on DAGs whenever$k-c$ is constant. In the same way, our work implies that $(k,c)$-SPC can besolved in polynomial time on undirected graphs whenever $k-c$ is constant.

A Local-to-Global Theorem for Congested Shortest Paths