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

Alon, Seymour, and Thomas generalized Lipton and Tarjan's planar separatortheorem and showed that a $K_h$-minor free graph with $n$ vertices has aseparator of size at most $h^{3/2}\sqrt n$. They gave an algorithm that, givena graph $G$ with $m$ edges and $n$ vertices and given an integer $h\geq 1$,outputs in $O(\sqrt{hn}m)$ time such a separator or a $K_h$-minor of $G$.Plotkin, Rao, and Smith gave an $O(hm\sqrt{n\log n})$ time algorithm to find aseparator of size $O(h\sqrt{n\log n})$. Kawarabayashi and Reed improved thebound on the size of the separator to $h\sqrt n$ and gave an algorithm thatfinds such a separator in $O(n^{1 + \epsilon})$ time for any constant $\epsilon> 0$, assuming $h$ is constant. This algorithm has an extremely largedependency on $h$ in the running time (some power tower of $h$ whose height isitself a function of $h$), making it impractical even for small $h$. We areinterested in a small polynomial time dependency on $h$ and we show how to findan $O(h\sqrt{n\log n})$-size separator or report that $G$ has a $K_h$-minor in$O(\poly(h)n^{5/4 + \epsilon})$ time for any constant $\epsilon > 0$. We alsopresent the first $O(\poly(h)n)$ time algorithm to find a separator of size$O(n^c)$ for a constant $c < 1$. As corollaries of our results, we get improvedalgorithms for shortest paths and maximum matching. Furthermore, for integers$\ell$ and $h$, we give an $O(m + n^{2 + \epsilon}/\ell)$ time algorithm thateither produces a $K_h$-minor of depth $O(\ell\log n)$ or a separator of sizeat most $O(n/\ell + \ell h^2\log n)$. This improves the shallow minor algorithmof Plotkin, Rao, and Smith when $m = \Omega(n^{1 + \epsilon})$. We get asimilar running time improvement for an approximation algorithm for the problemof finding a largest $K_h$-minor in a given graph.

Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications