On Vertex Ranking for Permutations and Other Graphs
On Vertex Ranking for Permutations and Other Graphs
复制标题
关于排列和其他图的顶点排序
DOI：
10.1007/3-540-57785-8_187
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
H. Müller
中科院分区：
文献类型：
--
作者：
J. Deogun;T. Kloks;D. Kratsch;H. Müller
本文证明了排列图的最优顶点排序可以在时间O（n6）内计算出来，其中n为顶点数。所演示的最小分隔方法也可用于设计多项式时间算法，计算以下结构良好的图类的最优顶点排序：圆置换图、间隔图、圆弧图、梯形图和有界维度的共比较图。
In this paper we show that an optimal vertex ranking of a permutation graph can be computed in time O(n6), where n is the number of vertices. The demonstrated minimal separator approach can also be used for designing polynomial time algorithms computing an optimal vertex ranking on the following classes of well-structured graphs: circular permutation graphs, interval graphs, circular arc graphs, trapezoid graphs and cocomparability graphs of bounded dimension.