Laying out Graphs Using Queues
Laying out Graphs Using Queues
复制标题
使用队列布局图
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
A. Rosenberg
中科院分区：
文献类型：
--
作者：
L. Heath;A. Rosenberg
研究了用队列来布置图边的问题。在k-queue布局中，图的顶点以某种线性顺序放置，并且每个边被分配给k个队列中的一个，以便分配给每个队列的边遵循先入先出的原则。该布局问题抽象了容错处理器阵列的设计问题、并行队列的排序问题和并行处理器的调度问题。建立了关于图的队列布局的一些基本结果，并将这些结果与图的堆栈布局（书嵌入问题）的类似结果进行了对比。描述了1队列图（它们几乎是水平平面图）。证明了1-队列图的识别问题是np完全的。给出了若干特定图类的队列布局。给出了图的队列号与其带宽和分隔符大小之间的关系。队列宽度和数量之间的明显权衡…
The problem of laying out the edges of a graph using queues is studied. In a k-queue layout, vertices of the graph are placed in some linear order and each edge is assigned to exactly one of the k queues so that the edges assigned to each queue obey a first-in/first-out discipline. This layout problem abstracts a design problem of fault-tolerant processor arrays, a problem of sorting with parallel queues, and a problem of scheduling parallel processors. A number of basic results about queue layouts of graphs are established, and these results are contrasted with their analogues for stack layouts of graphs (the book-embedding problem). The 1-queue graphs (they are almost leveled-planar graphs) are characterized. It is proved that the problem of recognizing 1-queue graphs is NP-complete. Queue layouts for some specific classes of graphs are given. Relationships between the queuenumber of a graph and its bandwidth and separator size are presented. An apparent tradeoff between the queuewidth and the number of...