Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number
Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number
复制标题
小宽度阶数和小迪尔沃斯数图的识别算法
DOI：
10.1023/b:orde.0000034609.99940.fb
复制
发表时间：
2003
期刊：
影响因子：
0.4
通讯作者：
J. Spinrad
中科院分区：
文献类型：
--
作者：
S. Felsner;V. Raghavan;J. Spinrad
小宽度偏序集和小Dilworth数图具有许多有趣的性质，并已得到很好的研究。在这里，我们表明，这样的订单和图形的识别可以更有效地比使用众所周知的算法的基础上二分匹配和矩阵乘法。特别地，我们证明了判定一个序是否有宽度k可以在O（kn2）时间内完成，而判定一个图是否有Dilworth数k可以在O（k2n2）时间内完成，对于很小的k，我们有更好的结果.我们证明了宽度不超过3的顺序可以在O（n）时间内识别，宽度不超过4的顺序可以在O（nlog n）时间内识别。
Partially ordered sets of small width and graphs of small Dilworth number have many interesting properties and have been well studied. Here we show that recognition of such orders and graphs can be done more efficiently than by using the well-known algorithms based on bipartite matching and matrix multiplication. In particular, we show that deciding deciding if an order has width k can be done in O(kn2) time and whether a graph has Dilworth number k can be done in O(k2n2) time.For very small k we have even better results. We show that orders of width at most 3 can be recognized in O(n) time and of width at most 4 in O(nlog n).