Древесная ширина графа: различия между версиями

Были предложены и экспериментально протестированы различные алгоритмы вычисления древесной ширины (эвристики нахождения верхней границы, эвристики нахождения нижней границы, точные алгоритмы и методы предварительной обработки). Обзор результатов многих подобных проверок приведен в работе [7]. Вариант алгоритма Арнборга и др.  [1] внедрили Шойхет и Гейгер [15]. Рориг [14] провел экспериментальную оценку алгоритма Бодлендера с линейным временем выполнения [4] и установил, что он оказывается непрактичным даже для малых значений k. Часто используются эвристики минимальной степени и минимального заполнения [10].