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

Digraphs H for which the list homomorphism problem with template H (LHOM(H))is in logspace (L) was characterized by Egri et al. (SODA 2014): LHOM(H) is inL if and only if H does not contain a circular N (assuming L is different fromNL). Undirected graphs for which LHOM(H) is in L can be characterized in termsforbidden induced subgraphs, and also via a simple inductive construction (Egriet al., STACS 2010). As a consequence, the logspace algorithm in the undirectedcase is simple and easy to understand. No such forbidden subgraph or inductivecharacterization, and no such simple and easy-to-understand algorithm is knownin the case of digraphs. In this paper, in the case of oriented trees, werefine and strengthen the results of Egri et al. (SODA 2014): we give acharacterization of oriented trees T for which LHOM(T) is in L both in terms offorbidden induced subgraphs, and also via a simple inductive construction.Using this characterization, we obtain a simple and easy-to-analyze logspacealgorithm for LHOM(T). We also show how these oriented trees can be recognizedin time O(|V(T)|^3) (the straightforward implementation of the algorithm givenin SODA 2014 runs in time O(|V(H)|^8) for oriented trees). An algebraiccharacterization of these trees is also provided.

Space complexity of list H-coloring revisited: the case of oriented trees