ALGORITHMS ON MARKED DIRECTED GRAPHS.

Marked directed graphs are a special case of Petri nets introduced as a model for information flow in systems exhibiting asynchromism and parallelism. Commoner, Holt, Even and Pneuli have studied several structural and algorithmic aspects of marked graphs using graph theory and network flow algorithms. Subsequently, Murata has studied graphs using a circuit-theoretic approach. The authors combine the ideas of both these works and present algorithms for certain problems on marked graphs. They introduce the concept of scatter in firing sequences and present algorithms for determining minimum scatter firing sequences for different classes of graphs. An approach for the general case is presented.