Stack and queue layouts of directed acyclic graphs: Part II

Stack layouts and queue layouts of undirected graphs have been used to mode l problems in fault tolerant computing and in parallel process scheduling. However, problems in parallel process scheduling are more accurately modele d by stack and queue layouts of directed acyclic graphs (dags). A stack lay out of a dag is similar to a stack layout of an undirected graph, with the additional requirement that the nodes of the dag be in some topological ord er. A queue layout is defined in an analogous manner. The stacknumber (queu enumber) of a dag is the smallest number of stacks (queues) required for it s stack layout (queue layout). This paper presents algorithmic results-in p articular, linear time algorithms for recognizing 1-stack dags and 1-queue dags, and proofs of NP-completeness for the problem of recognizing a 4-queu e dag and the problem of recognizing a 6-stack dag. The companion paper (Pa rt I [SIAM J. Comput., 28 (1999), pp. 1510-1539.]) presents combinatorial r esults.