|
Prikladnaya Diskretnaya Matematika, 2010, supplement № 3, Pages 99–101
(Mi pdm228)
|
|
|
|
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.
Citation:
E. A. Tatarinov, “Classes of graphs reconstructed with
linear time complexity”, Prikl. Diskr. Mat., 2010, supplement № 3, 99–101
Linking options:
https://www.mathnet.ru/eng/pdm228 https://www.mathnet.ru/eng/pdm/y2010/i12/p99
|
Statistics & downloads: |
Abstract page: | 130 | Full-text PDF : | 47 | References: | 50 |
|