The Complexity of the Partial Order Dimension Problem
The Complexity of the Partial Order Dimension Problem
复制标题
DOI：
10.1137/0603036
复制
发表时间：
1982-09
期刊：
影响因子：
--
通讯作者：
M. Yannakakis
中科院分区：
文献类型：
--
作者：
M. Yannakakis
一个偏序P的维度是交集为P的线性序的最小个数。我们证明了判定一个偏序是否具有3维是NP完全的，并由此证明了其它几个相关的维型问题也是NP完全的。
The dimension of a partial order P is the minimum number of linear orders whose intersection is P. There are efficient algorithms to test if a partial order has dimension 1 or 2. We prove that it is NP-complete to determine if a partial order has dimension 3. As a consequence, several other related dimension-type problems are shown to be NP-complete.