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/

Zendy Plus

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

Zendy Tools

Zendy Open

We investigate the locality number, a recently introduced structuralparameter for strings (with applications in pattern matching with variables),and its connection to two important graph-parameters, cutwidth and pathwidth.These connections allow us to show that computing the locality number isNP-hard, but fixed-parameter tractable, if parameterised by the locality numberor by the alphabet size, which has been formulated as open problems in theliterature. Moreover, the locality number can be approximated with ratioO(sqrt(log(opt)) log(n)). An important aspect of our work -- that is relevantin its own right and of independent interest -- is that we identify connectionsbetween the string parameter of the locality number on the one hand, and thefamous graph parameters of cutwidth and pathwidth, on the other hand. These twoparameters have been jointly investigated in the literature and are arguablyamong the most central graph parameters that are based on "linearisations" ofgraphs. In this way, we also identify a direct approximation preservingreduction from cutwidth to pathwidth, which shows that any polynomialf(opt,|V|)-approximation algorithm for pathwidth yields a polynomial 2f(2opt,h)-approximation algorithm for cutwidth on multigraphs (where h is thenumber of edges). In particular, this translates known approximation ratios forpathwidth into new approximation ratios for cutwidth, namely O(sqrt(log(opt))log(h)) and O(sqrt(log(opt)) opt) for (multi) graphs with h edges.

Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number