On the Vertex Ranking Problem for Trapezoid, Circular-arc and Other Graphs
On the Vertex Ranking Problem for Trapezoid, Circular-arc and Other Graphs
复制标题
关于梯形、圆弧等图的顶点排序问题
DOI：
10.1016/s0166-218x(99)00179-1
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
H. Müller
中科院分区：
文献类型：
--
作者：
J. Deogun;T. Kloks;D. Kratsch;H. Müller
我们提出了多项式时间算法来解决梯形图、置换图和圆弧图等不同图类的图的顶点排序问题。我们详细地展示了我们的方法对于称为d-梯形图和圆弧图的区间图和梯形图的推广。我们的所有算法都使用一种称为分段动态规划的方法。其中，它利用了所有极小分隔符和这些图的所有所谓片段都可以由相交模型的扫描线表示的特性。这使得多项式时间算法的设计能够列出所有最小分隔符和输入图的所有部分。
We present polynomial time algorithms to solve the VERTEX RANKING problem for graphs of various graph classes among them trapezoid graphs, permutation graphs and circular-arc graphs. We demonstrate our approach in detail for a generalization of interval and trapezoid graphs called d-trapezoid graphs and for circular-arc graphs. All our algorithms use an approach called dynamic programming on pieces. Among others it exploits the property that all minimal separators and all the so-called pieces of these graphs can be represented by scanlines of an intersection model. This enables the design of polynomial time algorithms to list both all minimal separators and all pieces of an input graph.