Быстрые алгоритмы ширины дерева

Я хотел бы вычислить ширину дерева графика. Есть действительно хорошая эвристика для других задач NP-сложных графов, таких как VF2 для изоморфизма подграфа, например, с кодом, доступным в igraph . Я попробовал их на своих графиках и обнаружил, что они работают очень быстро для моих данных.

Существуют ли быстрые алгоритмы для расчета ширины дерева в том же духе?

Насколько я знаю, уровень техники - это то, что сообщается в

Ханс Л. Бодлендер, Федор В. Фомин, Арье MCA Костер, Дитер Крач, и Димитриос М. Тиликос (2012), «О точных алгоритмах для определения ширины дерева», ACM Транзакции по алгоритмам 9 (1): A12, doi: 10.1145 / 2390176.2390188 ,

Методы, описанные там, включают реализованный алгоритм с некоторыми эвристическими оптимизациями, чтобы сделать его быстрее на практике.$O^*(2^n)$

Я написал статью под названием «Алгоритм быстрого параллельного ветвления и привязки для ширины дерева» в ICTAI 2011. Он может вычислять ширину дерева в многоядерном режиме . Я использовал много эвристики и потратил много времени на доработку программы.

Я был случайным студентом в Китае и не смог приехать на хорошую конференцию. Но, основываясь на результатах эксперимента, я думаю, что моя программа очень быстрая. Я решил множество нерешенных тестов в библиотеке Treewidth, и моя программа работала в 40 раз быстрее, чем алгоритм, предложенный Чжоу и Хансеном в IJCAI 09 ..

Я больше не работаю над этой темой. Но если моя предыдущая работа окажется полезной, вы можете загрузить мою программу (src и exe) с http://www.callowbird.com/undergraduate-stuff.html и попробовать. (все еще, это очень очень медленно на немного большем экземпляре)

$O^*(2^k)$

Вот два обзора алгоритмов для расчета ширины дерева, которые могут быть полезны. Первый имеет эмпирические сравнения, и он имеет различные алгоритмы, реализованные в виде библиотеки Java.

• treewidth.com / Вычисление treewidth с помощью Libtw Dijk, Heuvel, Slob

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

• Обнаружение Treewidth (2005) Хансом Л. Бодлендером

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

Sage не знает, как точно вычислить ширину дерева, но он может дать вам путь для небольших графиков.

http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_decompositions/vertex_separation.html

Я был бы очень рад узнать, что есть что-то реализованное и общедоступное для вычисления разложения дерева, хотя :-)

Nathann