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

Computing the directed path-width of a directed graph is an NP-hard problem.Even for digraphs of maximum semi-degree 3 the problem remains hard. We proposea decomposition of an input digraph G=(V,A) by a number k of sequences withentries from V, such that (u,v) in A if and only if in one of the sequencesthere is an occurrence of u appearing before an occurrence of v. We presentseveral graph theoretical properties of these digraphs. Among these we giveforbidden subdigraphs of digraphs which can be defined by k=1 sequence, whichis a subclass of semicomplete digraphs. Given the decomposition of digraph G,we show an algorithm which computes the directed path-width of G in timeO(k\cdot (1+N)^k), where N denotes the maximum sequence length. This leads toan XP-algorithm w.r.t. k for the directed path-width problem. Our resultimproves the algorithms of Kitsunai et al. for digraphs of large directedpath-width which can be decomposed by a small number of sequence.

Characterizations and Directed Path-Width of Sequence Digraphs