УДК 519.1
О стягивании циклов в ориентированных графах / П. В. Наливайко // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2010. № 3. С. 36-38.
Для решения задачи об отыскании в ориентированном графе ветвления минимального веса среди всех ветвлений максимальной мощности существует эффективный алгоритм, разработанный Тарьяном, основанный на технике стягивания циклов. В данной работе показывается, что эта техника применима и к более общей задаче, в которой на ветвление наложено дополнительное условие о том, что множество покрытых им вершин должно быть независимо относительно заданного матроида.
Ключевые слова: граф, ветвление, матроид, стягивание циклов.
Библиогр. 3.
