In this paper we introduce a family of ordered sets we call {\em
k-weak orders\/} which generalize weak orders, semi-orders, and
bipartite orders. For each $k$, we give a polynomial-time recognition
algorithm for $k$-weak orders and a partial characterization. In
addition, we prove that among 1-weak orders, the classes of bounded
bitolerance orders and totally bounded bitolerance orders are equal.
This enables us to recognize the class of totally bounded bitolerance
orders for 1-weak orders.
DIMACS Home Page