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

We introduce graph width parameters, called $\alpha$-edge-crossing width andedge-crossing width. These are defined in terms of the number of edges crossinga bag of a tree-cut decomposition. They are motivated by edge-cut width,recently introduced by Brand et al. (WG 2022). We show that edge-crossing widthis equivalent to the known parameter tree-partition-width. On the other hand,$\alpha$-edge-crossing width is a new parameter; tree-cut width and$\alpha$-edge-crossing width are incomparable, and they both lie betweentree-partition-width and edge-cut width.  We provide an algorithm that, for a given $n$-vertex graph $G$ and integers$k$ and $\alpha$, in time $2^{O((\alpha+k)\log (\alpha+k))}n^2$ either outputsa tree-cut decomposition certifying that the $\alpha$-edge-crossing width of$G$ is at most $2\alpha^2+5k$ or confirms that the $\alpha$-edge-crossing widthof $G$ is more than $k$. As applications, for every fixed $\alpha$, we obtainFPT algorithms for the List Coloring and Precoloring Extension problemsparameterized by $\alpha$-edge-crossing width. They were known to be W[1]-hardparameterized by tree-partition-width, and FPT parameterized by edge-cut width,and we close the complexity gap between these two parameters.

A new width parameter of graphs based on edge cuts: $\alpha$-edge-crossing width