Scientific Library of Tomsk State University

   E-catalog        

Normal view MARC view

Алгоритмы решения систем уравнений над различными классами конечных графов А. В. Ильев, В. П. Ильев

By: Ильев, Артем ВикторовичContributor(s): Ильев, Виктор ПетровичMaterial type: ArticleArticleContent type: Текст Media type: электронный Other title: Algorithms for solving systems of equations over various classes of finite graphs [Parallel title]Subject(s): графы | системы уравнений | вычислительная сложностьGenre/Form: статьи в журналах Online resources: Click here to access online In: Прикладная дискретная математика № 53. С. 89-102Abstract: Целью работы является исследование и решение конечных систем уравнений над конечными неориентированными графами. Уравнениями над графами называются атомарные формулы языка L, состоящего из множества констант (вершин графа), бинарного предиката смежности вершин и предиката равенства. Доказано, что задача проверки совместности системы уравнений S от k переменных над произвольным обыкновенным n-вершинным графом Г является N P -полной. Подсчитана вычислительная сложность процедуры проверки совместности системы уравнений S над обыкновенным графом Г и процедуры нахождения общего решения этой системы. Вычислительная сложность алгоритма решения системы уравнений S от k переменных над произвольным обыкновенным n-вершинным графом Г, включающего эти процедуры, составляет O(k2nk/2+1(k+ n )2) при n @ 3. Выделены полиномиально разрешимые случаи: системы уравнений над деревьями, лесами, двудольными и полными двудольными графами, для решения которых предложены полиномиальные алгоритмы трудоёмкости O(k2n(k + n)2).
Tags from this library: No tags from this library for this title. Log in to add tags.
No physical items for this record

Библиогр.: 13 назв.

Целью работы является исследование и решение конечных систем уравнений над конечными неориентированными графами. Уравнениями над графами называются атомарные формулы языка L, состоящего из множества констант (вершин графа), бинарного предиката смежности вершин и предиката равенства. Доказано, что задача проверки совместности системы уравнений S от k переменных над произвольным обыкновенным n-вершинным графом Г является N P -полной. Подсчитана вычислительная сложность процедуры проверки совместности системы уравнений S над обыкновенным графом Г и процедуры нахождения общего решения этой системы. Вычислительная сложность алгоритма решения системы уравнений S от k переменных над произвольным обыкновенным n-вершинным графом Г, включающего эти процедуры, составляет O(k2nk/2+1(k+ n )2) при n @ 3. Выделены полиномиально разрешимые случаи: системы уравнений над деревьями, лесами, двудольными и полными двудольными графами, для решения которых предложены полиномиальные алгоритмы трудоёмкости O(k2n(k + n)2).

There are no comments on this title.

to post a comment.
Share