Analysis of cactus graphs using automata: properties and recognition
time

Demidova Anna Andreevna

Analysis of cactus graphs using automata: properties and recognition time

Demidova A. A.

Demidova Anna Andreevna

graduate student, Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Chair of Mathematical Theory of Intellectual Systems

Published: 2023, vol. 27, issue 2, pp. 111–124

Download full text (In Russian)

Abstract

This paper is devoted to the study of using automata with erasable colors to determine whether an arbitrary connected plane simple undirected graph is a cactus. An algorithm is given for determining this property, as well as lower and upper bounds of the number of steps that the automaton must take to complete the traversal.

Keywords: automata, graphs, cactus graphs.

BibTeX

@article{IS-Demidova2023,
  author  = {Demidova, Anna Andreevna},
  title   = {{Analysis of cactus graphs using automata: properties and recognition time}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2023},
  volume  = {27},
  number  = {2},
  pages   = {111--124},
}

AMSBIB

\Bibitem{IS-Demidova2023}
\by A.\,A.~Demidova
\paper Analysis of cactus graphs using automata: properties and recognition time
\jour Intelligent Systems. Theory and Applications
\yr 2023
\vol 27
\issue 2
\pages 111--124
\lang In Russian

Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue