Scientific Library of Tomsk State University

   E-catalog        

Normal view MARC view

Алгоритмы решения систем уравнений над различными классами конечных графов (Record no. 723365)

000 -Маркер записи
Контрольное поле постоянной длины 03177nab a2200325 c 4500
001 - Контрольный номер
Контрольное поле koha000723365
005 - Дата корректировки
Контрольное поле 20230616122813.0
007 - Кодируемые данные (физ. описан.)
Контрольное поле постоянной длины cr |
008 - Кодируемые данные
Контрольное поле постоянной длины 211214|2021 ru s c rus d
024 7# - Прочие стандартные номера
Стандартный номер 10.17223/20710410/53/6
Источник номера doi
035 ## - Системный контрольный номер
Системный контрольный номер koha000723365
040 ## - Источник каталогиз.
Служба первич. каталог. RU-ToGU
Код языка каталог. rus
Служба, преобразующая запись RU-ToGU
100 1# - Автор
Автор Ильев, Артем Викторович
9 (RLIN) 458301
245 10 - Заглавие
Заглавие Алгоритмы решения систем уравнений над различными классами конечных графов
Ответственность А. В. Ильев, В. П. Ильев
246 11 - Заглавие тома/части
Заглавие тома/части Algorithms for solving systems of equations over various classes of finite graphs
336 ## - Тип содержимого
Тип содержимого Текст
337 ## - Средство доступа
Средство доступа электронный
504 ## - Библиография
Библиография Библиогр.: 13 назв.
520 3# - Аннотация
Аннотация Целью работы является исследование и решение конечных систем уравнений над конечными неориентированными графами. Уравнениями над графами называются атомарные формулы языка L, состоящего из множества констант (вершин графа), бинарного предиката смежности вершин и предиката равенства. Доказано, что задача проверки совместности системы уравнений S от k переменных над произвольным обыкновенным n-вершинным графом Г является N P -полной. Подсчитана вычислительная сложность процедуры проверки совместности системы уравнений S над обыкновенным графом Г и процедуры нахождения общего решения этой системы. Вычислительная сложность алгоритма решения системы уравнений S от k переменных над произвольным обыкновенным n-вершинным графом Г, включающего эти процедуры, составляет O(k2nk/2+1(k+ n )2) при n @ 3. Выделены полиномиально разрешимые случаи: системы уравнений над деревьями, лесами, двудольными и полными двудольными графами, для решения которых предложены полиномиальные алгоритмы трудоёмкости O(k2n(k + n)2).
653 ## - Ключевые слова
Ключевые слова графы
653 ## - Ключевые слова
Ключевые слова системы уравнений
653 ## - Ключевые слова
Ключевые слова вычислительная сложность
655 #4 - Термин индексирования — жанр/форма
Жанр/форма статьи в журналах
9 (RLIN) 879358
700 ## - Другие авторы
Другие авторы Ильев, Виктор Петрович
9 (RLIN) 351292
773 0# - Источник информации
Название источника Прикладная дискретная математика
Место и дата издания 2021
Прочая информация № 53. С. 89-102
ISSN 2071-0410
Контрольный № источника 0210-48760
852 4# - Местонахождение единицы хранения
Код организации-хранителя RU-ToGU
856 4# - Электронный адрес документа
URL <a href="http://vital.lib.tsu.ru/vital/access/manager/Repository/koha:000723365">http://vital.lib.tsu.ru/vital/access/manager/Repository/koha:000723365</a>
908 ## - Параметр входа данных
Параметр входа данных статья
999 ## - Системные контрольные номера (Koha)
biblionumber (Koha) 723365

No items available.