Аннотация:
Рассматривается задача выделения всех бикомпонент ориентированного графа, число дуг в котором достаточно велико. Предлагается достроить исследуемый граф до полного и выделять бикомпоненты в полном орграфе, используя специальные показатели, содержащие необходимую информацию в агрегированном виде. Показано, что алгоритм, использующий данную идею, позволяет за $O(n^2)$ операций решить задачу или хотя бы осуществить ее декомпозицию, причем при наличии некоторой предварительной информации эта оценка может быть улучшена до $O(n)$.