The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 28 NO.4 / (1999))
Stack and Queue Layouts of Directed Acyclic Graph:Part I
Lenwood S. Heath, Sriram V. Pemmaraju, Ann. N Trenk,
Pages. 1510-1539
Abstract Stack layouts and queue layouts of undirected graphs have been used to model problems in fault-tolerant computing and in parallel process scheduling.
However, problems in parallel process scheduling are more accurately modeled by
stack and queue layouts of directed acyclic graphs (dags). A stack layout of a
dag is similar to a stack layout of an undirected graph, with the additions
requirement that the nodes of the dag be in some topological order. A queue
layout is defined in an analogous manner. The stacknumber (queuenumber) of a dag
is the smallest number of stacks (queues) required for its stack layout (queue
layout). In this paper, bounds are established on the stacknumber and
queuenumber of two classes of dags: tree dags and unicyclic dags. In particular,
any tree dag can be laid out in 1 stack and in at most 2 queues; and unicyclic
dag can be laid out in at most 2 stacks and in at most 2 queues. Forbidden
subgraph characterizations of 1-queue tree dags and 1-queue cycle dags are also
presented. Part II of this paper presents algorithmic results-in particular,
linear time algorithms for recognizing 1-stack dags and 1-queue dags and proof
of NP- completeness for the problem of recognizing a 4-queue dag and the problem
of recognizing a 9-stack dag.
Contents 1. Preliminaries
2. Stack layouts of dags
3. Queue layouts of dags
4. Characterization of 1-queue directed trees and directed cycles
4.1. Characterization of 1-queue directed trees
4.2. Characterization of 1-queue directed cycles
5. Conclusion
Key words stack layout, queue layout, book embedding, graph embedding, directed acyclic graphs, dags, forbidden subgraph
Mathmatical Subject Classification 05C99, 68Q15, 68Q25, 68R10, 94