Кто-нибудь знает о программе с открытым исходным кодом для вычисления дерева разложения графов для фиксированной "k" (ширина)? Я знаю, что проблема поиска Tree-Decomposition является NP-Hard для переменной «k», но мои входные экземпляры будут очень маленькими (~ 10 узлов), и «k» исправлена.
22
Ответы:
Некоторые из этих программ могут вам помочь. (Не все из них с открытым исходным кодом.)
* TreeD http://www.itu.dk/people/sathi/treed/
* dlib http://dlib.net/
* QuickBB http://www.cs.washington.edu/homes/vgogate/quickbb.html
* Hypertree http://www.dbai.tuwien.ac.at/proj/hypertree/downloads.html
* LibTW http://www.treewidth.com/treewidth/
источник
Если и фиксированы, то вы даже можете позволить себе использовать алгоритм XP, подобный тому, который мы реализовали для нашего приложения для Android. Исходный код находится здесь: TreewidthInspector , и, например, при и он заканчивается менее чем за секунду.п ~ 10 К n ≤ 13 k ≤ 4
Это примерно 170 строк кода и это GPL (или MIT, или BSD, или все, что вам нужно).
источник
Для вы можете использовать по адресу http://treedecompositions.com/, чтобы напрямую получать и визуализировать быструю и разумную декомпозицию без необходимости что-либо компилировать или устанавливать.n ≤ 150
источник
LibTW еще можно найти. Это на http://www.treewidth.com/treewidth/ .
источник
Вас также могут заинтересовать более современные алгоритмы FlowCutter ( GitHub ) и алгоритмы Tamaki et al. ( GitHub )
источник