Journal article
Stack and Queue Layouts of Directed Acyclic Graphs: Part II
SIAM journal on computing, Vol.28(5), pp.1588-1626
01/1999
DOI: 10.1137/S0097539795291550
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 additional 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). This paper presents algorithmic results - in particular, linear time algorithms for recognizing 1-stack dags and 1-queue dags, and proofs of NP-completeness for the problem of recognizing a 4-queue dag and the problem of recognizing a 6-stack dag. The companion paper (Part I [SIAM J. Comput., 28 (1999), pp. 1510-1539.]) presents combinatorial results.
Details
- Title: Subtitle
- Stack and Queue Layouts of Directed Acyclic Graphs: Part II
- Creators
- Lenwood S. HeathSriram V. Pemmaraju
- Resource Type
- Journal article
- Publication Details
- SIAM journal on computing, Vol.28(5), pp.1588-1626
- DOI
- 10.1137/S0097539795291550
- ISSN
- 0097-5397
- eISSN
- 1095-7111
- Language
- English
- Date published
- 01/1999
- Academic Unit
- Computer Science
- Record Identifier
- 9984259499202771
Metrics
19 Record Views