Article ID Journal Published Year Pages File Type
423602 Electronic Notes in Theoretical Computer Science 2008 14 Pages PDF
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