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

In this paper we show how to combine two algorithmic techniques to obtainlinear time algorithms for various optimization problems on graphs, and presenta subroutine which will be useful in doing so.  The first technique is iterative shrinking. In the first phase of aniterative shrinking algorithm, we construct a sequence of graphs of decreasingsize $G_1,\ldots,G_\ell$ where $G_1$ is the initial input, $G_\ell$ is a graphon which the problem is easy, and $G_i$ is obtained from $G_{i+1}$ via someshrinking algorithm. In the second phase we work through the sequence inreverse, repeatedly constructing a solution for a graph from the solution forits successor. In an iterative compaction algorithm, we insist that the graphsdecrease by a constant fraction of the entire graph.  Another approach to solving optimization problems is to exploit thestructural properties implied by the connectivity of the input graph. Thisapproach can be used on graphs which are not highly connected by decomposing aninput graph into its highly connected pieces, solving subproblems on thesespecially structured pieces and then combining their solutions.  We combine these two techniques by developing compaction algorithms whichwhen applied to the highly connected pieces preserve their connectivityproperties. The structural properties this connectivity implies can be helpfulboth in finding further compactions in later iterations and when we aremanipulating solutions in the second phase of an iterative compactionalgorithm.  To illustrate how this compaction algorithm can be used as a subroutine, wepresent a linear time algorithm that given four vertices $\{s_1,s_2,t_1,t_2\}$of a graph $G$, either finds a pair of disjoint paths $P_1$ and $P_2$ of $G$such that $P_i$ has endpoints $s_i$ and $t_i$, or returns a planar embedding ofan auxiliary graph which shows that no such pair exists.

Connectivity Preserving Iterative Compaction and Finding 2 Disjoint Rooted Paths in Linear Time