Базовый алгоритм восстановления конечного графа

Рассматривается задача восстановления графа агентом, перемещающимся по его ребрам, считывающим и изменяющим метки на элементах графа. Предложен базовый метод восстановления. Алгоритм требует 2 различные краски и кубического, от числа вершин графа, числа шагов. Найдены модификации алгоритма, которые...

Full description

Saved in:

Bibliographic Details
Published in:	Труды Института прикладной математики и механики
Date:	2010
Main Author:	Татаринов, Е.А.
Format:	Article
Language:	Russian
Published:	Інститут прикладної математики і механіки НАН України 2010
Online Access:	https://nasplib.isofts.kiev.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

id	nasplib_isofts_kiev_ua-123456789-123970
record_format	dspace
spelling	Татаринов, Е.А. 2017-09-15T17:35:42Z 2017-09-15T17:35:42Z 2010 Базовый алгоритм восстановления конечного графа / Е.А. Татаринов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 216-227. — Бібліогр.: 9 назв. — рос. 1683-4720 https://nasplib.isofts.kiev.ua/handle/123456789/123970 519.5 Рассматривается задача восстановления графа агентом, перемещающимся по его ребрам, считывающим и изменяющим метки на элементах графа. Предложен базовый метод восстановления. Алгоритм требует 2 различные краски и кубического, от числа вершин графа, числа шагов. Найдены модификации алгоритма, которые понижают верхнюю оценку временной сложности. Найдены операции над графами, результирующий граф которых имеет верхнюю оценку сложности выполнения базового алгоритма не хуже, чем исходный. Розглядається задача відновлення графа агентом, який переміщується по його ребрах, що прочитує ізмінює мітки на елементах графа. Запропоновано базовий метод відновлення. Алгоритм потребує 2 різні фарби і кубічного, від числа вершин графа, числа кроків. Знайдено модифікації алгоритму, які знижують верхню оцінку часової складності. Знайдено операції над графами, результуючий граф яких має верхню оцінку складності виконання базового алгоритму не гірше, ніж вихідний. The problem of reconstructing a graph agent moving through his edges, read and modify marks on the elements of the graph. We propose a basic method of reconstruction. The algorithm requires 2 different colors and cube of the number of vertices number of steps. Found modification of the algorithm, which lowers the upper bound of time complexity. Found the operation on graphs, the resulting graph which has an upper bound for the complexity of the basic algorithm is not worse than the original. ru Інститут прикладної математики і механіки НАН України Труды Института прикладной математики и механики Базовый алгоритм восстановления конечного графа Базовий алгоритм відновлення скінченного графа Basic algorithm for reconstructing a finite graph Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Базовый алгоритм восстановления конечного графа
spellingShingle	Базовый алгоритм восстановления конечного графа Татаринов, Е.А.
title_short	Базовый алгоритм восстановления конечного графа
title_full	Базовый алгоритм восстановления конечного графа
title_fullStr	Базовый алгоритм восстановления конечного графа
title_full_unstemmed	Базовый алгоритм восстановления конечного графа
title_sort	базовый алгоритм восстановления конечного графа
author	Татаринов, Е.А.
author_facet	Татаринов, Е.А.
publishDate	2010
language	Russian
container_title	Труды Института прикладной математики и механики
publisher	Інститут прикладної математики і механіки НАН України
format	Article
title_alt	Базовий алгоритм відновлення скінченного графа Basic algorithm for reconstructing a finite graph
description	Рассматривается задача восстановления графа агентом, перемещающимся по его ребрам, считывающим и изменяющим метки на элементах графа. Предложен базовый метод восстановления. Алгоритм требует 2 различные краски и кубического, от числа вершин графа, числа шагов. Найдены модификации алгоритма, которые понижают верхнюю оценку временной сложности. Найдены операции над графами, результирующий граф которых имеет верхнюю оценку сложности выполнения базового алгоритма не хуже, чем исходный. Розглядається задача відновлення графа агентом, який переміщується по його ребрах, що прочитує ізмінює мітки на елементах графа. Запропоновано базовий метод відновлення. Алгоритм потребує 2 різні фарби і кубічного, від числа вершин графа, числа кроків. Знайдено модифікації алгоритму, які знижують верхню оцінку часової складності. Знайдено операції над графами, результуючий граф яких має верхню оцінку складності виконання базового алгоритму не гірше, ніж вихідний. The problem of reconstructing a graph agent moving through his edges, read and modify marks on the elements of the graph. We propose a basic method of reconstruction. The algorithm requires 2 different colors and cube of the number of vertices number of steps. Found modification of the algorithm, which lowers the upper bound of time complexity. Found the operation on graphs, the resulting graph which has an upper bound for the complexity of the basic algorithm is not worse than the original.
issn	1683-4720
url	https://nasplib.isofts.kiev.ua/handle/123456789/123970
citation_txt	Базовый алгоритм восстановления конечного графа / Е.А. Татаринов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 216-227. — Бібліогр.: 9 назв. — рос.
work_keys_str_mv	AT tatarinovea bazovyialgoritmvosstanovleniâkonečnogografa AT tatarinovea bazoviialgoritmvídnovlennâskínčennogografa AT tatarinovea basicalgorithmforreconstructingafinitegraph
first_indexed	2025-12-07T16:03:13Z
last_indexed	2025-12-07T16:03:13Z
_version_	1850866027693342720

Базовый алгоритм восстановления конечного графа

Institution

Similar Items