УДК 519.1

О стягивании циклов в ориентированных графах  / П. В. Наливайко // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2010. ? 3. С. 36-38.

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

Ключевые слова: граф, ветвление, матроид, стягивание циклов.

Библиогр. 3.