Optimal algorithm for converting an acyclic digraph to a cluster

G. Sh. Tsitsiashvili ; M. A. Osipova

Prikladnaâ diskretnaâ matematika, no. 4 (2021), pp. 94-98

Résumé

A bipartite digraph $\widehat{G}$ with edges from the first part $V_1$ to the second part $V_2$ is considered. The minimum edge cover in the digraph $\widehat{G}$ consists of a set of unrelated stars $G_1^1,\ldots,G_1^M$ with a root in $V_1$ and stars $G_2^1,\ldots,G_2^N$ with a root in $V_2$. Denote by $m$ the number of leaves in the stars $G_1^1,\ldots,G_1^M$ and by $n$ the number of leaves in the stars $G_2^1,\ldots,G_2^N$ and put $p(\widehat{G})$ the minimum number of additional edges, the introduction of which into the digraph $\widehat{G}$ transforms it into a strongly connected digraph. It is proved that: 1) $p(\widehat{G})=\max(m+N,n+M)$; 2) $p(\widehat{G})=\max(|V_1|,|V_2|)$; 3) $p(\mathcal{G})=\max(|\mathcal{V}_1|,|\mathcal{V}_2|)$ for an acyclic digraph $\mathcal{G}$, where $\mathcal{V}_1$ is the set of vertices of $\mathcal{G}$, from which the arcs only leave, $\mathcal{V}_2$ — the set of vertices of $\mathcal{G}$, into which the arcs only enter. Algorithms for determining the minimum set of additional edges have been proposed. They are based on finding the minimum edge coverage in a bipartite graph and connecting unconnected stars with the minimum number of edges.

Détail

Keywords: acyclic digraph, cluster, Hamiltonian cycle, feedback, minimal edge cover.
Mots-clés : bipartite digraph