Математическая модель и алгоритм вычисления циклов ячеек карты графа

Авторы

DOI:

https://doi.org/10.26089/NumMet.v22r419

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

карта графа, ячейки карты, циклы графа, свойства циклов

Аннотация

Выделенные свойства циклов DFS-базиса блока карты простого графа позволили составить математическую модель вычисления циклов ячеек карты графа. По данной модели предложен практический алгоритм вычисления циклов ячеек карты графа. Алгоритм имеет квадратическую сложность относительно числа вершин в графе.

Автор

Б. Н. Иванов

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

  1. B. N. Ivanov, “Solution of the Optimal Ship Route Problem in the Framework of the OKEAN Geoinformation System,” Vychisl. Metody Programm. 13 (1), 226-234 (2012).
  2. J. T. Welch, “A Mechanical Analysis of the Cyclic Structure of Undirected Linear Graphs,” J. Assoc. Comput. Mach. 13 (2), 205-210 (1966).
  3. N. E. Gibbs, “A Cycle Generation Algorithm for Finite Undirected Linear Graphs,” J. Assoc. Comput. Mach. 16 (4), 564-568 (1969).
  4. R. Tarjan, “Enumeration of the Elementary Circuits of a Directed Graph,” SIAM J. Comput. 2 (3), 211-216 (1973).
  5. D. B. Jonson, “Finding all the Elementary Circuits of a Directed Graph,” SIAM J. Comput. 4 (1), 77-84 (1975).
  6. P. Mateti and N. Deo, “On Algorithms for Enumerating all Circuits of a Graph,” SIAM J. Comput. 5 (1), 90-99 (1976).
  7. R. Tarjan, “Depth-First Search Linear Graph Algorithms,” SIAM J. Comput. 1 (2), 146-160 (1972).
  8. F. Mahdi, M. Safar, and K. Mahdi, “Detecting Cycles in Graphs Using Parallel Capabilities of GPU,” in Digital Information and Communication Technology and Its Applications (Springer, Berlin, 2011), Vol. 167, pp. 193-205.
  9. T. Kavitha, K. Mehlhorn, and D. Michail, “New Approximation Algorithms for Minimum Cycle Bases of Graphs,” Algorithmica 59 (4), 471-488 (2011).
  10. J. L. Pfaltz, “Chordless Cycles in Networks,” in Proc. IEEE 29th Int. Conf. on Data Engineering Workshops, Brisbane, Australia, April 8-12, 2013 (IEEE Press, New York, 2013), pp. 223-228.
  11. B. N. Ivanov, “Generation of Cycles of Map Cells for a Simple Planar Graph,” Vychisl. Metody Programm. 15 (2), 304-316 (2014).
  12. O. Ore, Theory of Graphs (AMS Press, Providence, 1962; Nauka, Moscow, 1980).
  13. F. P. Preparatat and M. I. Shamos, Computational Geometry: An Introduction (Springer, Heidelberg, 1985; Mir, Moscow, 1989).
  14. B. E. Alekseev and V. A. Talanov, Graphs. Computational Models. Structures (Lobachevsky State Univ. of Nizhni Novgorod, Nizhni Novgorod, 2005) [in Russian].
  15. K. Paton, “An Algorithm for Finding a Fundamental Set of Cycles of a Graph,” Commun. ACM 12 (9), 514-518 (1969).
  16. E. M. Reingold, J. Nievergelt, and N. Deo, Combinatorial Algorithms. Theory and Practice (Prentice-Hall, Englewood Cliffs, 1977; Mir, Moscow, 1980).
  17. B. N. Ivanov, “Nesting Structures of the Isoline Field in the Gradient Filling Problem,” Vychisl. Metody Programm. 7 (2), 30-40 (2006).

Загрузки

Опубликован

30-11-2021

Как цитировать

Иванов Б. Н. Математическая модель и алгоритм вычисления циклов ячеек карты графа // Вычислительные методы и программирование. 2021. 22. 294-305. doi 10.26089/NumMet.v22r419

Выпуск

Раздел

Методы и алгоритмы вычислительной математики и их приложения