Normal view
MARC view
Алгоритмы решения систем уравнений над различными классами конечных графов (Record no. 723365)
[ view plain ]
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.