Генерация циклов ячеек карты простого планарного графа

Авторы

  • Б.Н. Иванов

Ключевые слова:

генерация циклов
перечисление циклов
базис циклов
карта графа
вложенность циклов
фундаментальные циклы
chordless cycles

Аннотация

Рассматривается конструктивный метод генерации циклов ячеек (chordless cycles) карты простого планарного графа. Циклы ячеек карты представляются как линейные комбинации циклов {DFS-базиса}. Искомые линейные комбинации строятся явно на основе выделенных свойств структуры вложенности циклов базиса и циклов ячеек карты графа. Карта планарного графа позволила отойти от общепринятого подхода генерации циклов и явно внести геометрию карты в структуру алгоритма. На множестве циклов базиса определяется отношение соседства, которое порождает корневые деревья структуры вложенности циклов. Ячейки карты графа являются результатом обхода данного множества корневых деревьев. Сложность предложенного алгоритма является кубической относительно числа вершин в графе. Рассматривается приложение алгоритма в рамках решения задач на планарном подразбиении.

Новые вычислительные технологии

Загрузки

Опубликован

2014-05-16

Выпуск

Том 15 (2014): Выпуск 2.

Раздел

Раздел 1. Вычислительные методы и приложения

Автор

Б.Н. Иванов

Дальневосточный федеральный университет (ДВФУ),
Школа естественных наук
ул. Суханова, 8, 690091, Владивосток
• доцент

Библиографические ссылки

  1. Иванов Б.Н. Решение задачи расчета оптимальных маршрутов судов в рамках геоинформационной системы «ОКЕАН» // Вычислительные методы и программирование. 2012. 13. 226-234.
  2. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. М.: Мир, 1989.
  3. Оре О. Теория графов. М.: Наука, 1980.
  4. Роджерс К.А. Укладки и покрытия. М.: Мир, 1968.
  5. Делоне Б.Н. О пустом шаре // Известия АН СССР. 1934. VII серия, № 6. 793-800.
  6. Sokhn N., Baltensperger R., Bersier L.F., Hennebert J., Ultes-Nitsche U. Identification of chordless cycles in ecological networks // Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering. Vol. 126. Berlin: Springer, 2013. 316-324.
  7. Pfaltz J.L. Chordless cycles in networks // IEEE 29th International Conference on Data Engineering Workshops (ICDEW). New York: IEEE Press, 2013. 223-228.
  8. Welch J. A mechanical analysis of the cyclic structure of undirected linear graphs // J. Assoc. Comput. Mech. 1966. 13. 205-210.
  9. Gibbs N.W. A cycle generation algorithm for finite undirected linear graphs // J. Assoc. Comput. Mech. 1969. 16. 564-568.
  10. Tarjan R. Enumeration of the elementary circuits of a directed graph // SIAM J. Comput. 1973. 2, N 3. 211-216.
  11. Jonson D.B. Finding all the elementary circuits of a directed graph // SIAM J. Comput. 1975. 4, N 1. 77-84.
  12. Mateti P., Deo N. On algorithms for enumerating all circuits of a graph // SIAM J. Comput. 1976. 5, N 1. 90-99.
  13. Tarjan R.E. Depth-first search linear graph algorithms // SIAM J. Comput. 1972. 1. 146-160.
  14. Syslo M.M. An efficient cycle vector space algorithm for listing all cycles of a planar graph // SIAM J. Comput. 1981. 10, N 4. 797-808.
  15. Wild M. Generating all cycles, chordless cycles, and Hamiltonian cycles with the principle of exclusion // Journal of Discrete Algorithms. 2008. 6. 93-102.
  16. Mahdi F., Safar M., Mahdi K. Detecting cycles in graphs using parallel capabilities of GPU // Digital Information and Communication Technology and Its Applications. Vol. 167. Berlin: Springer, 2011. 193-205.
  17. Kavitha T., Mehlhorn K., Michail D. New approximation algorithms for minimum cycle bases of graphs // Algorithmica. 2011. 59, N 4. 471-488.
  18. Рейнголд Э., Нивергельд Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980.
  19. Курош А.Г. Лекции по общей алгебре. М.: Наука, 1973.
  20. Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Структуры. Нижний Новгород: Изд-во ННГУ, 2005.
  21. Dogrusoz U., Krishnamoorthy M.S. Enumerating all cycles of a planar graph // Parallel Algorithms Appl. 1996. 10, N 1/2. 21-36.
  22. Deo N., Prabhu G.M., Krishnamoorthy M.S. Algorithms for generating fundamental cycles in a graph // ACM Trans. Math. Software. 1982. 8, N 1. 26-42.
  23. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. М.: Известия, 2011.
  24. Paton K. An algorithm for finding a fundamental set of cycles of a graph // Comm. ACM. 1969. 12, N 9. 514-518.
  25. Иванов Б.Н. Структуры вложенности поля изолиний в задаче градиентного заполнения // Вычислительные методы и программирование. 2006. 7, № 1. 155-165.

Лицензия

Copyright (c) 2014 Вычислительные методы и программирование

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.