An Atlas of Edge-Reverse Dynamics
This book is a reference volume on the dynamics of scheduling by edge reversal (SER), i.e., on transformations of acyclic graphs by changing sinks (nodes with arcs oriented inward) to sources (nodes with arcs oriented outward). The author first introduces scheduling by edge reversal as a mechanism to rebuild communication routes in computer networks after topological changes. Other possible applications of this formalism are given. In particular, the author discusses a description of resource-sharing systems (like the well known dining philosophers problem) and networks of automata (e.g., Hopfield neural networks or Bayesian networks). The next topics are the basic properties of SER and an enumeration of the SER state space. The major part of the book consists of a repository of graphical representations of SER basins of attraction for some selected graphs. In particular, all graphs on six nodes, all trees on seven nodes, and all rings on three to eight nodes are covered. The book is easy to read and understand thanks to many examples. It is intended to be a repository of results and data. Thus, proofs for many results are omitted, but a comprehensive set of references where these proofs can be found is given.