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/

Zendy Plus

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

Zendy Tools

Zendy Open

We study the problem of routing on disjoint paths in bounded treewidth graphswith both edge and node capacities. The input consists of a capacitated graph$G$ and a collection of $k$ source-destination pairs $\mathcal{M} = \{(s_1,t_1), \dots, (s_k, t_k)\}$. The goal is to maximize the number of pairs thatcan be routed subject to the capacities in the graph. A routing of a subset$\mathcal{M}'$ of the pairs is a collection $\mathcal{P}$ of paths such that,for each pair $(s_i, t_i) \in \mathcal{M}'$, there is a path in $\mathcal{P}$connecting $s_i$ to $t_i$. In the Maximum Edge Disjoint Paths (MaxEDP) problem,the graph $G$ has capacities $\mathrm{cap}(e)$ on the edges and a routing$\mathcal{P}$ is feasible if each edge $e$ is in at most $\mathrm{cap}(e)$ ofthe paths of $\mathcal{P}$. The Maximum Node Disjoint Paths (MaxNDP) problem isthe node-capacitated counterpart of MaxEDP.  In this paper we obtain an $O(r^3)$ approximation for MaxEDP on graphs oftreewidth at most $r$ and a matching approximation for MaxNDP on graphs ofpathwidth at most $r$. Our results build on and significantly improve the workby Chekuri et al. [ICALP 2013] who obtained an $O(r \cdot 3^r)$ approximationfor MaxEDP.

On Routing Disjoint Paths in Bounded Treewidth Graphs