Preview

Труды Института системного программирования РАН

Расширенный поиск

Построение прямого и обратного остовов автоматами на графе

https://doi.org/10.15514/ISPRAS-2014-26(6)-4

Полный текст:

Аннотация

В работе представлен алгоритм параллельного исследования графа. Автомат на графе является аналогом машины Тьюринга - ячейки ленты соответствуют вершинам графа, где автомат может сохранять некоторую информацию, а движение по ленте соответствует движениям по дугам графа. Такая система может рассматриваться также как совокупность автоматов, размещенных в вершинах графа и взаимодействующих путем посылки сообщений по дугам. Каждый автомат изменяет свое состояние в соответствии с данными, сохраняемыми в вершине, а движение по дугам заменяется посылкой сообщений. Время работы предлагаемого алгоритма параллельного исследования графа ограничено сверху O(n/k+D), где n - число вершин графа, D - диаметр графа, максимальная длина простого пути (пути без самопересечений). В результате работы алгоритма строится два остова графа: прямой остов, корнем которого является корневая вершина графа, ориентированный от корня, и обратный остов, ориентированный к корню.

Об авторах

Игорь Бурдонов
Институт Системного Программирования РАН
Россия


Александр Косачев
Институт Системного Программирования РАН
Россия


Список литературы

1. Steven S. Skiena. The Algorithm Design Manual. Springer-Verlag, New York, 1997.

2. И.Б. Бурдонов, А.С. Косачев, В.В. Кулямин. "Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай" // Программирование, 2003 г., №5, с. 59-69.

3. И.Б. Бурдонов, А.С. Косачев, В.В. Кулямин. "Неизбыточные алгоритмы обхода ориентированных графов. Недетерминированный случай" // Программирование, 2004 г., №1, с. 2-17.

4. M.O. Rabin. Maze Threading Automata. An unpublished lecture presented at MIT and UC, Berkeley, 1967.

5. И.Б. Бурдонов. "Обход неизвестного ориентированного графа конечным роботом" // Программирование, 2004 г., № 4, с. 11-34.

6. И.Б. Бурдонов. "Проблема отката по дереву при обходе неизвестного ориентированного графа конечным роботом" // Программирование, 2004 г., № 6, с. 6-29.

7. Б. Бурдонов, А.С. Косачев, В.В. Кулямин. "Параллельные вычисления на графе"// Программирование, 2015 г., № 1, с. 3-20.


Для цитирования:


Бурдонов И., Косачев А. Построение прямого и обратного остовов автоматами на графе. Труды Института системного программирования РАН. 2014;26(6):57-62. https://doi.org/10.15514/ISPRAS-2014-26(6)-4

For citation:


Burdonov I., Kossachev A. Building direct and back spanning trees by automata on a graph. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2014;26(6):57-62. (In Russ.) https://doi.org/10.15514/ISPRAS-2014-26(6)-4

Просмотров: 30


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)