Оптимальный алгоритм преобразования ациклического орграфа в сильносвязный

Для двудольного орграфа $G$, в котором все дуги выходят из первой доли во вторую, решена задача нахождения минимального набора дуг, дополнение которых преобразует его в сильносвязный орграф. Доказано, что минимальное число дополнительных дуг, преобразующих двудольный орграф $G$ в сильносвязный, равно максимуму из числа вершин первой и второй долей. Построен алгоритм определения минимального набора дополнительных дуг, преобразующих данный орграф в сильносвязный. Этот алгоритм основан на выделении минимального рёберного покрытия, как совокупности несвязанных между собой звезд в орграфе $G$, и на построении дуг, соединяющих эти звезды. Полученный результат использован для нахождения минимального набора дуг, преобразующих произвольный ациклический орграф в сильносвязный орграф путём выделения рёбер, соединяющих звёзды в минимальном рёберном покрытии. Данная задача возникла при анализе биотехнологических решений, повышающих стабильность функционирования белковых сетей за счёт введения в них обратных связей.