Applied Theory of Coding, Automata and Graphs

Classes of graphs reconstructed with linear time complexity

E. A. Tatarinov

Institute of Applied Mathematics and Mechanics, Donetsk, Ukraine

Abstract: A graph exploration problem is considered by means of an agent which moves on graph edges, coloures the marks on it's nodes and its incidentors. The agent reconstructs a graph which is isomorphic to the recognized one by using information about marks on graph nodes and incidentors. A proposed recognition methods have quadratic and cubic complexity and need no more then four different marks. Classes of graphs with linear complexity of recognition are found. For them some operations on graphs preserving the linear complexity of recognition are defined.

UDC: 519.5