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

A simple digraph is semi-complete if for any two of its vertices $u$ and $v$,at least one of the arcs $(u,v)$ and $(v,u)$ is present. We study thecomplexity of computing two layout parameters of semi-complete digraphs:cutwidth and optimal linear arrangement (OLA). We prove that: (1) Bothparameters are $\mathsf{NP}$-hard to compute and the known exact andparameterized algorithms for them have essentially optimal running times,assuming the Exponential Time Hypothesis; (2) The cutwidth parameter admits aquadratic Turing kernel, whereas it does not admit any polynomial kernel unless$\mathsf{NP}\subseteq \mathsf{coNP}/\textrm{poly}$. By contrast, OLA admits alinear kernel. These results essentially complete the complexity analysis ofcomputing cutwidth and OLA on semi-complete digraphs. Our techniques can bealso used to analyze the sizes of minimal obstructions for having smallcutwidth under the induced subdigraph relation.

Exploring the complexity of layout parameters in tournaments and semi-complete digraphs