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 a graph $G$ and an integer $b$, Bandwidth asks whether there exists abijection $\pi$ from $V(G)$ to $\{1, \ldots, |V(G)|\}$ such that $\max_{\{u, v\} \in E(G)} | \pi(u) - \pi(v) | \leq b$. This is a classical NP-completeproblem, known to remain NP-complete even on very restricted classes of graphs,such as trees of maximum degree 3 and caterpillars of hair length 3. In therealm of parameterized complexity, these results imply that the problem remainsNP-hard on graphs of bounded pathwidth, while it is additionally known to beW[1]-hard when parameterized by the treedepth of the input graph. In contrast,the problem does become FPT when parameterized by the vertex cover number ofthe input graph. In this paper, we make progress towards the parameterized(in)tractability of Bandwidth. We first show that it is FPT when parameterizedby the cluster vertex deletion number cvd plus the clique number $\omega$ ofthe input graph, thus generalizing the previously mentioned result for vertexcover. On the other hand, we show that Bandwidth is W[1]-hard whenparameterized only by cvd. Our results generalize some of the previous resultsand narrow some of the complexity gaps.

Bandwidth Parameterized by Cluster Vertex Deletion Number