Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
423602 | Electronic Notes in Theoretical Computer Science | 2008 | 14 Pages |
Abstract
We study complexity problems involving three sorts of combinational structures: cyclic orders, order varieties and cycles. It is known that the problem of telling whether a cyclic order is included in some cycle is NP-complete. We show that the same question for order varieties, a special class of cyclic orders, is in L. For this, we relate the entropy relation between partial orders to the forcing relation of graph theory.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics