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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

An out-branching $B^+_u$ (in-branching $B^-_u$) in a digraph $D$ is aconnected spanning subdigraph of $D$ in which every vertex except the vertex$u$, called the root, has in-degree (out-degree) one. A {\bf good$\mathbf{(u,v)}$-pair} in $D$ is a pair of branchings $B^+_u,B^-_v$ which haveno arc in common.  Thomassen proved that is NP-complete to decide if a digraph has any goodpair. A digraph is {\bf semicomplete} if it has no pair of non adjacentvertices. A {\bf semicomplete composition} is any digraph $D$ which is obtainedfrom a semicomplete digraph $S$ by substituting an arbitrary digraph $H_x$ foreach vertex $x$ of $S$.  Recently the authors of this paper gave a complete classification ofsemicomplete digraphs which have a good $(u,v)$-pair, where $u,v$ areprescribed vertices of $D$. They also gave a polynomial algorithm which for agiven semicomplete digraph $D$ and vertices $u,v$ of $D$, either produces agood $(u,v)$-pair in $D$ or a certificate that $D$ has such pair. In this paperwe show how to use the result for semicomplete digraphs to completely solve theproblem of deciding whether a given semicomplete composition $D$, has a good$(u,v)$-pair for given vertices $u,v$ of $D$. Our solution implies that theproblem is polynomially solvable for all semicomplete compositions. Inparticular our result implies that there is a polynomial algorithm for decidingwhether a given quasi-transitive digraph $D$ has a good $(u,v)$-pair for givenvertices $u,v$ of $D$. This confirms a conjecture of Bang-Jensen and Gutin from1998.

Arc-disjoint out- and in-branchings in compositions of digraphs