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

For digraphs $G$ and $H$, a homomorphism of $G$ to $H$ is a mapping $f:\V(G)\dom V(H)$ such that $uv\in A(G)$ implies $f(u)f(v)\in A(H)$. If, moreover,each vertex $u \in V(G)$ is associated with costs $c_i(u), i \in V(H)$, thenthe cost of a homomorphism $f$ is $\sum_{u\in V(G)}c_{f(u)}(u)$. For each fixeddigraph $H$, the minimum cost homomorphism problem for $H$, denotedMinHOM($H$), can be formulated as follows: Given an input digraph $G$, togetherwith costs $c_i(u)$, $u\in V(G)$, $i\in V(H)$, decide whether there exists ahomomorphism of $G$ to $H$ and, if one exists, to find one of minimum cost.Minimum cost homomorphism problems encompass (or are related to) many wellstudied optimization problems such as the minimum cost chromatic partition andrepair analysis problems. We focus on the minimum cost homomorphism problem forlocally semicomplete digraphs and quasi-transitive digraphs which are twowell-known generalizations of tournaments. Using graph-theoreticcharacterization results for the two digraph classes, we obtain a fulldichotomy classification of the complexity of minimum cost homomorphismproblems for both classes.

Minimum Cost Homomorphisms to Locally Semicomplete and Quasi-Transitive Digraphs