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

Linear rank-width is a linearized variation of rank-width, and it is deeplyrelated to matroid path-width. In this paper, we show that the linearrank-width of every $n$-vertex distance-hereditary graph, equivalently a graphof rank-width at most $1$, can be computed in time $\mathcal{O}(n^2\cdot \log_2n)$, and a linear layout witnessing the linear rank-width can be computed withthe same time complexity. As a corollary, we show that the path-width of every$n$-element matroid of branch-width at most $2$ can be computed in time$\mathcal{O}(n^2\cdot \log_2 n)$, provided that the matroid is given by anindependent set oracle.  To establish this result, we present a characterization of the linearrank-width of distance-hereditary graphs in terms of their canonical splitdecompositions. This characterization is similar to the known characterizationof the path-width of forests given by Ellis, Sudborough, and Turner [The vertexseparation and search number of a graph. Inf. Comput., 113(1):50--79, 1994].However, different from forests, it is non-trivial to relate substructures ofthe canonical split decomposition of a graph with some substructures of thegiven graph. We introduce a notion of `limbs' of canonical splitdecompositions, which correspond to certain vertex-minors of the originalgraph, for the right characterization.

Linear rank-width of distance-hereditary graphs I. A polynomial-time algorithm