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

Let $G=(V,E)$ be a directed graph with $n$ vertices and $m$ edges. The graph$G$ is called singly-connected if for each pair of vertices $v,w \in V$ thereis at most one simple path from $v$ to $w$ in $G$. Buchsbaum and Carlisle(1993) gave an algorithm for testing whether $G$ is singly-connected in$O(n^{2})$ time. In this paper we describe a refined version of this algorithmwith running time $O(s\cdot t+m)$, where $s$ and $t$ are the number of sourcesand sinks, respectively, in the reduced graph $G^{r}$ obtained by firstcontracting each strongly connected component of $G$ into one vertex and theneliminating vertices of indegree or outdegree $1$ by a contraction operation.Moreover, we show that the problem of finding a minimum cardinality edge subset$C\subseteq E$ (respectively, vertex subset $F\subseteq V$) whose removal from$G$ leaves a singly-connected graph is NP-hard.

On testing single connectedness in directed graphs and some related problems