Линейный алгоритм для нахождения максимального индуцированного паросочетания наименьшего веса в реберно-взвешенном дереве

Индуцированным паросочетанием в графе $G$ называется множество ребер порожденного $1$-регулярного подграфа. Индуцированное паросочетание $M$ графа $G$ называется максимальным, если оно не содержится в индуцированном паросочетании с большим числом ребер. Предложен алгоритм, который задачу построения максимального индуцированного паросочетания наименьшего веса в реберно-взвешенном дереве решает за линейное время.
Библиогр. 21 назв.