On k-weak orders: Recognition and a tolerance result Original Research Article

In this paper we introduce a family of ordered sets we call k-weak orders which generalize weak orders, semi-orders, and bipartite orders. For each fixed 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.