Graph theory for programmers. Algorithms for processing trees

Authors V. A. Evstigneev, Victor N. Kasyanov

Publication date 12 October 2000

algorithms data retrieval data structures flow graphs monograph program structure spanning trees

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Graph theory (including graph drawing) in computer science (68R10)

Review text

This is a reference work on algorithmic aspects of trees. It does a remarkably good job of treating a number of major topics in enough detail to serve as an excellent introduction, but gives a very compact presentation. To quote the authors: ``This book is intended not only to be a reference book of algorithms but also an introduction to the theory of graphs that studies trees and their applications. We make an attempt to give a concise but more or less complete description of basic notions, properties, and fields of applications of trees. We clearly understand that it is impossible to include in the monograph all known algorithms but, at the same time, we have a hope that our collection is sufficiently representative. The authors have succeeded in their goals; certainly both graph theorists and computer scientists will find the treatment covers topics of interest well. The book is organized in three parts, treating main definitions and algorithms, applications in program structure (especially language representation and parsing), and applications in data retrieval, in turn. Chapter 1, Trees and their properties, gives basic definitions, codes for trees, and enumerative formulas. In Chapter 2, Computational models, a basic machine model is introduced and basic search and generation algorithms are described. Chapter 3, Spanning trees, completes the first part with algorithms for optimal spanning trees, for all spanning trees, and for trees with various restrictions. Chapter 4, Structural trees, studies control flow graphs for models of program execution. In Chapter 5, the fundamental notion of tree isomorphism is explored, and trees arising in term rewriting systems are studied. Chapter 6, Syntax trees, develops the notion of parse trees in language recognition. This completes the second part. Chapter 7, Information trees, examines trees as data structures and treats balanced trees in some detail. The third part is concluded with Chapter 8, Trees for multilevel memory, which examines B-trees. The selection of topics is weighted towards ``mainstream computer science applications, and gives a clear exposition of these. It differs from many sources in data structures in that the treatment of the underlying combinatorics of trees is much more extensive in this book, with the result that a graph theorist and a computer scientist will both find much familiar material, but also much new material. The references provided are quite useful, but perhaps not as extensive as a reader might wish. Nevertheless, on the topics treated, the book is relatively comprehensive. In conclusion, this book is a useful text for algorithms and computer science applications of trees.

Recommendations

Cited in

(9)

This page was built for publication: Graph theory for programmers. Algorithms for processing trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4509236)