Базовый алгоритм восстановления конечного графа
Рассматривается задача восстановления графа агентом, перемещающимся по его ребрам, считывающим и изменяющим метки на элементах графа. Предложен базовый метод восстановления. Алгоритм требует 2 различные краски и кубического, от числа вершин графа, числа шагов. Найдены модификации алгоритма, которые...
Saved in:
| Date: | 2010 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут прикладної математики і механіки НАН України
2010
|
| Series: | Труды Института прикладной математики и механики |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/123970 |
| 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: | Базовый алгоритм восстановления конечного графа / Е.А. Татаринов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 216-227. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| Summary: | Рассматривается задача восстановления графа агентом, перемещающимся по его ребрам, считывающим и изменяющим метки на элементах графа. Предложен базовый метод восстановления. Алгоритм требует 2 различные краски и кубического, от числа вершин графа, числа шагов. Найдены модификации алгоритма, которые понижают верхнюю оценку временной сложности. Найдены операции над графами, результирующий граф которых имеет верхнюю оценку сложности выполнения базового алгоритма не хуже, чем исходный. |
|---|