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

Consider an undirected graph $G = (VG, EG)$ and a set of six \emph{terminals}$T = \set{s_1, s_2, s_3, t_1, t_2, t_3} \subseteq VG$. The goal is to find acollection $\calP$ of three edge-disjoint paths $P_1$, $P_2$, and $P_3$, where$P_i$ connects nodes $s_i$ and $t_i$ ($i = 1, 2, 3$). Results obtained byRobertson and Seymour by graph minor techniques imply a polynomial timesolvability of this problem. The time bound of their algorithm is $O(m^3)$(hereinafter we assume $n := \abs{VG}$, $m := \abs{EG}$, $n = O(m)$). In thispaper we consider a special, \emph{Eulerian} case of $G$ and $T$. Namely,construct the \emph{demand graph} $H = (VG, \set{s_1t_1, s_2t_2, s_3t_3})$. Theedges of $H$ correspond to the desired paths in $\calP$. In the Eulerian casethe degrees of all nodes in the (multi-) graph $G + H$ ($ = (VG, EG \cup EH)$)are even. Schrijver showed that, under the assumption of Eulerianess, cutconditions provide a criterion for the existence of $\calP$. This, inparticular, implies that checking for existence of $\calP$ can be done in$O(m)$ time. Our result is a combinatorial $O(m)$-time algorithm thatconstructs $\calP$ (if the latter exists).

A Linear Time Algorithm for Finding Three Edge-Disjoint Paths in Eulerian Networks