×

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
Full Text: Link