Нашли опечатку? Выделите ее мышкой и нажмите Ctrl+Enter
Название: Mathematical Programming Study 13. Combinatorial optimization II
Автор: Rayward-Smith V.
The problem of determining whether a graph has a Hamilton cycle is NP-complete whereas there exists a polynomial algorithm to determine whether a graph has a perfect 2-matching.
These two problems are related to the question of determining whether a graph has a perfect triangle-free 2-matching. We give a polynomial algorithm to answer this question and to find a perfect triangle-free 2-matching if one exists.