Solution Counting for CSP and SAT with Large Tree-Width
Рассмотрена проблема подсчета количества решений задачи совместимости ограничений (Constraint Satisfaction Problem). Для ее решения был адаптирован метод обратного прослеживания с ацикличным представлением графа ограничений (Backtracking with Tree-Decomposition). Предложен точный алгоритм, сложность...
Saved in:
| Published in: | Управляющие системы и машины |
|---|---|
| Date: | 2011 |
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Published: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/82919 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Solution Counting for CSP and SAT with Large Tree-Width / A. Favier, S. de Givry, Ph. Jégou // Управляющие системы и машины. — 2011. — № 2. — С. 4-13, 70. — Бібліогр.: 36 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862618431911624704 |
|---|---|
| author | Favier, A. de Givry, S. Jégou, P. |
| author_facet | Favier, A. de Givry, S. Jégou, P. |
| citation_txt | Solution Counting for CSP and SAT with Large Tree-Width / A. Favier, S. de Givry, Ph. Jégou // Управляющие системы и машины. — 2011. — № 2. — С. 4-13, 70. — Бібліогр.: 36 назв. — англ. |
| collection | DSpace DC |
| container_title | Управляющие системы и машины |
| description | Рассмотрена проблема подсчета количества решений задачи совместимости ограничений (Constraint Satisfaction Problem). Для ее решения был адаптирован метод обратного прослеживания с ацикличным представлением графа ограничений (Backtracking with Tree-Decomposition). Предложен точный алгоритм, сложность которого экспоненциально зависит от ширины дерева, и приближенный алгоритм, экспоненциально зависящий от размера максимальной клики.
The problem of counting the number of solutions of a CSP is considered. For solving the problem the Backtracking with a Tree-Decomposition method was adapted. The exact algorithm is suggested which has the worst-time complexity exponential in a tree width, as well as iterative algorithm that has computational complexity exponential in a maximum clique size.
Розглянуто проблему підрахунку кількості розв’язків задачі сумісності обмежень (Constraint Satisfaction Problem). Для її розв’язку було адаптовано метод зворотного простеження з ациклічним поданням графа обмежень (Backtracking with Tree-Decomposition). Запропоновано точний алгоритм, складність якого експоненційно залежить від ширини дерева, і наближений алгоритм, експоненційно залежний від розміру максимальної кліки.
|
| first_indexed | 2025-12-07T13:13:54Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-82919 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0130-5395 |
| language | English |
| last_indexed | 2025-12-07T13:13:54Z |
| publishDate | 2011 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| record_format | dspace |
| spelling | Favier, A. de Givry, S. Jégou, P. 2015-06-11T20:00:01Z 2015-06-11T20:00:01Z 2011 Solution Counting for CSP and SAT with Large Tree-Width / A. Favier, S. de Givry, Ph. Jégou // Управляющие системы и машины. — 2011. — № 2. — С. 4-13, 70. — Бібліогр.: 36 назв. — англ. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/82919 519.157 Рассмотрена проблема подсчета количества решений задачи совместимости ограничений (Constraint Satisfaction Problem). Для ее решения был адаптирован метод обратного прослеживания с ацикличным представлением графа ограничений (Backtracking with Tree-Decomposition). Предложен точный алгоритм, сложность которого экспоненциально зависит от ширины дерева, и приближенный алгоритм, экспоненциально зависящий от размера максимальной клики. The problem of counting the number of solutions of a CSP is considered. For solving the problem the Backtracking with a Tree-Decomposition method was adapted. The exact algorithm is suggested which has the worst-time complexity exponential in a tree width, as well as iterative algorithm that has computational complexity exponential in a maximum clique size. Розглянуто проблему підрахунку кількості розв’язків задачі сумісності обмежень (Constraint Satisfaction Problem). Для її розв’язку було адаптовано метод зворотного простеження з ациклічним поданням графа обмежень (Backtracking with Tree-Decomposition). Запропоновано точний алгоритм, складність якого експоненційно залежить від ширини дерева, і наближений алгоритм, експоненційно залежний від розміру максимальної кліки. en Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Оптимизационные задачи структурного распознавания образов Solution Counting for CSP and SAT with Large Tree-Width Подсчет количества решений задач CSP и SAT на деревьях большой ширины Підрахунок кількості розв’язків задач CSP та SAT на деревах великої ширини Article published earlier |
| spellingShingle | Solution Counting for CSP and SAT with Large Tree-Width Favier, A. de Givry, S. Jégou, P. Оптимизационные задачи структурного распознавания образов |
| title | Solution Counting for CSP and SAT with Large Tree-Width |
| title_alt | Подсчет количества решений задач CSP и SAT на деревьях большой ширины Підрахунок кількості розв’язків задач CSP та SAT на деревах великої ширини |
| title_full | Solution Counting for CSP and SAT with Large Tree-Width |
| title_fullStr | Solution Counting for CSP and SAT with Large Tree-Width |
| title_full_unstemmed | Solution Counting for CSP and SAT with Large Tree-Width |
| title_short | Solution Counting for CSP and SAT with Large Tree-Width |
| title_sort | solution counting for csp and sat with large tree-width |
| topic | Оптимизационные задачи структурного распознавания образов |
| topic_facet | Оптимизационные задачи структурного распознавания образов |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/82919 |
| work_keys_str_mv | AT faviera solutioncountingforcspandsatwithlargetreewidth AT degivrys solutioncountingforcspandsatwithlargetreewidth AT jegoup solutioncountingforcspandsatwithlargetreewidth AT faviera podsčetkoličestvarešeniizadačcspisatnaderevʹâhbolʹšoiširiny AT degivrys podsčetkoličestvarešeniizadačcspisatnaderevʹâhbolʹšoiširiny AT jegoup podsčetkoličestvarešeniizadačcspisatnaderevʹâhbolʹšoiširiny AT faviera pídrahunokkílʹkostírozvâzkívzadačcsptasatnaderevahvelikoíširini AT degivrys pídrahunokkílʹkostírozvâzkívzadačcsptasatnaderevahvelikoíširini AT jegoup pídrahunokkílʹkostírozvâzkívzadačcsptasatnaderevahvelikoíširini |