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

Authors

DOI:

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

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.

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

Downloads

Published

30-11-2021

How to Cite

Иванов Б.Н. Mathematical Model and Algorithm for Calculating the Cycles of the Cells of the Graph Map // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2021. 22. 294-305. doi 10.26089/NumMet.v22r419

Issue

Vol. 22 (2021): Issue 4.

Section

Methods and algorithms of computational mathematics and their applications

License

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

Creative Commons License

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