|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Прикладная теория графов
Алгоритмы решения систем уравнений над различными классами конечных графов
А. В. Ильевa, В. П. Ильевb a Институт математики им. С. Л. Соболева СО РАН, г. Омск, Россия
b Омский государственный университет им. Ф. М. Достоевского, г. Омск, Россия
Аннотация:
Целью работы является исследование и решение конечных систем уравнений над конечными неориентированными графами. Уравнениями над графами называются атомарные формулы языка ${\rm L}$, состоящего из множества констант (вершин графа), бинарного предиката смежности вершин и предиката равенства. Доказано, что задача проверки совместности системы уравнений $S$ от $k$ переменных над произвольным обыкновенным $n$-вершинным графом $\Gamma$ является $\mathcal{NP}$-полной. Подсчитана вычислительная сложность процедуры проверки совместности системы уравнений $S$ над обыкновенным графом $\Gamma$ и процедуры нахождения общего решения этой системы. Вычислительная сложность алгоритма решения системы уравнений $S$ от $k$ переменных над произвольным обыкновенным $n$-вершинным графом $\Gamma$, включающего эти процедуры, составляет $O(k^2n^{k/2+1}(k+n)^2)$ при ${n \geq 3}$. Выделены полиномиально разрешимые случаи: системы уравнений над деревьями, лесами, двудольными и полными двудольными графами, для решения которых предложены полиномиальные алгоритмы трудоёмкости $O(k^2n(k+n)^2)$.
Ключевые слова:
граф, система уравнений, вычислительная сложность.
Образец цитирования:
А. В. Ильев, В. П. Ильев, “Алгоритмы решения систем уравнений над различными классами конечных графов”, ПДМ, 2021, № 53, 89–102
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm748 https://www.mathnet.ru/rus/pdm/y2021/i3/p89
|
Статистика просмотров: |
Страница аннотации: | 157 | PDF полного текста: | 155 | Список литературы: | 26 |
|