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

Minimum $k$-Section denotes the NP-hard problem to partition the vertex setof a graph into $k$ sets of sizes as equal as possible while minimizing the cutwidth, which is the number of edges between these sets. When $k$ is an inputparameter and $n$ denotes the number of vertices, it is NP-hard to approximatethe width of a minimum $k$-section within a factor of $n^c$ for any $c<1$, evenwhen restricted to trees with constant diameter. Here, we show that every tree$T$ allows a $k$-section of width at most $(k-1) (2 + 16n / diam(T) )\Delta(T)$. This implies a polynomial-time constant-factor approximation forthe Minimum $k$-Section Problem when restricted to trees with linear diameterand constant maximum degree. Moreover, we extend our results from trees toarbitrary graphs with a given tree decomposition.

Approximating the Minimum $k$-Section Width in Bounded-Degree Trees with Linear Diameter