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

Let $G$ be a directed graph with $n$ vertices, $m$ edges, and non-negativeedge costs. Given $G$, a fixed source vertex $s$, and a positive integer $p$,we consider the problem of computing, for each vertex $t\neq s$, $p$edge-disjoint paths of minimum total cost from $s$ to $t$ in $G$. Suurballe andTarjan~[Networks, 1984] solved the above problem for $p=2$ by designing a$O(m+n\log n)$ time algorithm which also computes a sparse \emph{single-source$2$-multipath preserver}, i.e., a subgraph containing $2$ edge-disjoint pathsof minimum total cost from $s$ to every other vertex of $G$. The case $p \geq3$ was left as an open problem.  We study the general problem ($p\geq 2$) and prove that any graph admits asparse single-source $p$-multipath preserver with $p(n-1)$ edges. This size isoptimal since the in-degree of each non-root vertex $v$ must be at least $p$.Moreover, we design an algorithm that requires $O(pn^2 (p + \log n))$ time tocompute both $p$ edge-disjoint paths of minimum total cost from the source toall other vertices and an optimal-size single-source $p$-multipath preserver.The running time of our algorithm outperforms that of a natural approach thatsolves $n-1$ single-pair instances using the well-known \emph{successiveshortest paths} algorithm by a factor of $\Theta(\frac{m}{np})$ and isasymptotically near optimal if $p=O(1)$ and $m=\Theta(n^2)$. Our results extendnaturally to the case of $p$ vertex-disjoint paths.

Finding single-source shortest $p$-disjoint paths: fast computation and sparse preservers