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

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Given an undirected graph and two disjoint vertex pairs $s_1,t_1$ and$s_2,t_2$, the Shortest two disjoint paths problem (S2DP) asks for the minimumtotal length of two vertex disjoint paths connecting $s_1$ with $t_1$, and$s_2$ with $t_2$, respectively.  We show that for cubic planar graphs there are NC algorithms, uniformcircuits of polynomial size and polylogarithmic depth, that compute the S2DPand moreover also output the number of such minimum length path pairs.  Previously, to the best of our knowledge, no deterministic polynomial timealgorithm was known for S2DP in cubic planar graphs with arbitrary placement ofthe terminals. In contrast, the randomized polynomial time algorithm byBj\"orklund and Husfeldt, ICALP 2014, for general graphs is much slower, isserial in nature, and cannot count the solutions.  Our results are built on an approach by Hirai and Namba, Algorithmica 2017,for a generalisation of S2DP, and fast algorithms for counting perfectmatchings in planar graphs.

Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm