Stack and Queue Layouts of Directed Acyclic Graphs: Part I
Stack and Queue Layouts of Directed Acyclic Graphs: Part I
复制标题
有向无环图的堆栈和队列布局：第一部分
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
Ann N. Trenk
中科院分区：
文献类型：
--
作者：
Lenwood S. Heath;Sriram V. Pemmaraju;Ann N. Trenk
无向图的堆栈布局和队列布局已用于模拟易于故障计算和并行过程调度中的问题。但是，在并行过程调度中的问题更准确地通过有向无环图（DAG）的堆栈和队列布局来建模。 DAG的堆栈布局类似于无向图的堆栈布局，并要求dag的节点以某种拓扑顺序为单位。队列布局以类似的方式定义。 DAG的堆栈（Queuenumber）是其堆栈布局（队列布局）所需的最少数量的堆栈（队列）。在本文中，在两类dags的堆叠和queuenumber上建立了界限：树dags和unicclic dags。特别是，任何树dag都可以在1个堆栈中布置，最多可以在2个队列中列出；任何一个单车DAG最多都可以在2个堆栈中布置，最多可以排在2个队列中。还介绍了1 Queue Tree Dag和1-Queucue Cycle DAG的禁止子图表征。本文的第二部分介绍了算法结果 - 特别是，识别1堆栈DAG和1 Queue DAG的线性时间算法以及NP完整性的证明，以识别4个标题DAG的问题以及识别识别A的问题9-stack dag。
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). 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 any 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.