Solution Counting for CSP and SAT with Large Tree-Width

Favier, A.; de Givry, S.; Jegou, P.

Favier A.
Solution Counting for CSP and SAT with Large Tree-Width / A. Favier, S. de Givry, P. Jegou // Управляющие системы и машины. - 2011. - № 2. - С. 4-13, 70. - Режим доступу: http://nbuv.gov.ua/UJRN/USM_2011_2_3

Рассмотрена проблема подсчета количества решений задачи совместимости ограничений (Constraint Satisfaction Problem). Для ее решения был адаптирован метод обратного прослеживания с ацикличным представлением графа ограничений (Backtracking with Tree-Decomposition). Предложен точный алгоритм, сложность которого экспоненциально зависит от ширины дерева, и приближенный алгоритм, экспоненциально зависящий от размера максимальной клики.

Повний текст PDF - 962.515 Kb

Зміст випуску Google Scholar

Цитування публікації

Цитованість авторів публікації:

Favier A.

de Givry S.

Jegou P.

Бібліографічний опис для цитування:

Favier A. Solution Counting for CSP and SAT with Large Tree-Width / A. Favier, S. de Givry, P. Jegou // Управляющие системы и машины. - 2011. - № 2. - С. 4-13, 70. - Режим доступу: http://nbuv.gov.ua/UJRN/USM_2011_2_3.

Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"

Відділ інформаційно-комунікаційних технологій

Пам`ятка користувача


	Наукова періодика України		Control systems & computers