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

Bibliographie

[1] Tarjan R., “Dehpt-first search and linear graph algorithms”, SIAM J. Comput., 1:2 (1972), 146–160 | DOI | MR | Zbl

[2] Tsitsiashvili G. Sh., Osipova M. A., Losev A. S., “Graph clustering algorithms”, Bull. Voronezh State University. Ser. Physics, Math., 2016, no. 1, 145–149 (in Russian) | Zbl

[3] Alekseev V. E., Zakharova D. V., Graph Theory, tutorial, Nizhny Novgorod State University, N. Novgorod, 2017, 119 pp. (in Russian)

[4] Graph Theory, 2017

[5] Cormen T. H., Leiserson Ch. E., Rivest R. L., Stein Cl., Introduction to Algorithms, 3rd Ed., MIT Press, Cambridge, 2009, 499 pp. | MR | Zbl