Skobelev, V. G. Local algorithms on graphs. (Локальные алгоритмы на графах.) (Russian) Zbl 1349.05001 Donetsk: Natsional’naya Akademiya Nauk Ukrainy, Institut Prikladnoĭ Matematiki i Mekhaniki (ISBN 966-02-2987-9). 217 p. (2003). Publisher’s description: The monograph is devoted to the study of the solvability of graph theory problems in algorithm classes with linear capacitive complexity and algorithms with linear complexity of working memory. For different graph representations, we study the complexity of graph operations, as well as the complexity of the solution the tasks of constructing all the main types of paths, cycles, and spanning trees. It is shown that a number of model problems of discrete mathematics and its applications (identification of states of a finite automaton, construction supervisor for an automaton model of a system of discrete events, the construction of a winning strategy in 2-person games on the graph) is not solvable in the considered classes of algorithms.For specialists in discrete mathematics, graph theory and computer science, students and graduate students specializing in these areas, as well as for specialists whose research is associated with the development and analysis of algorithms in both theoretical and applied aspects. MSC: 05-02 Research exposition (monographs, survey articles) pertaining to combinatorics 05C85 Graph algorithms (graph-theoretic aspects) 68R10 Graph theory (including graph drawing) in computer science 68W05 Nonnumerical algorithms PDFBibTeX XMLCite \textit{V. G. Skobelev}, Локальные алгоритмы на графах (Russian). Donetsk: Natsional'naya Akademiya Nauk Ukrainy, Institut Prikladnoĭ Matematiki i Mekhaniki (2003; Zbl 1349.05001) Full Text: Link