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

Mathematical model and algorithm for calculating the cycles of the cells of the graph map

Authors

  • Boris N. Ivanov

Keywords:

graph map
map cells
graph cycles
cycle properties

Abstract

The selected properties of the cycles of the DFS-basis block of a simple graph map allowed us to create a mathematical model for calculating the cycles of the cells of the graph map. According to this model, a practical algorithm for calculating the cycles of the graph map cells is proposed. The algorithm has a quadratic complexity relative to the number of vertices in the graph.

Downloads

Published

2021-11-30

Issue

Vol. 22 (2021): Issue 4.

Section

Methods and algorithms of computational mathematics and their applications

Author Biography

Boris N. Ivanov

Far Eastern Federal University (FEFU),
• Associate Professor

References

  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).

License

Copyright (c) 2021 Б.Н. Иванов

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.