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

The graph parameter of pathwidth can be seen as a measure of the topologicalresemblance of a graph to a path. A popular definition of pathwidth is given interms of node search where we are given a system of tunnels that iscontaminated by some infectious substance and we are looking for a searchstrategy that, at each step, either places a searcher on a vertex or removes asearcher from a vertex and where an edge is cleaned when both endpoints aresimultaneously occupied by searchers. It was proved that the minimum number ofsearchers required for a successful cleaning strategy is equal to the pathwidthof the graph plus one. Two desired characteristics for a cleaning strategy isto be monotone (no recontamination occurs) and connected (clean territoriesalways remain connected). Under these two demands, the number of searchers isequivalent to a variant of pathwidth called {\em connected pathwidth}. We provethat connected pathwidth is fixed parameter tractable, in particular we designa $2^{O(k^2)}\cdot n$ time algorithm that checks whether the connectedpathwidth of $G$ is at most $k.$ This resolves an open question by[Dereniowski, Osula, and Rz{\k{a}}{\.{z}}ewski, Finding small-width connectedpath-decompositions in polynomial time. Theor. Comput. Sci., 794:85-100, 2019].For our algorithm, we enrich the typical sequence technique that is able todeal with the connectivity demand. Typical sequences have been introduced in[Bodlaender and Kloks. Efficient and constructive algorithms for the pathwidthand treewidth of graphs. J. Algorithms, 21(2):358-402, 1996] for the design oflinear parameterized algorithms for treewidth and pathwidth. The proposedextension is based on an encoding of the connectivity property that is quiteversatile and may be adapted so to deliver linear parameterized algorithms forthe connected variants of other width parameters as well.

A linear fixed parameter tractable algorithm for connected pathwidth