DIMACS TR: 96-12

k-Weak Orders: Recognition and a Tolerance Result

Author: Ann N. Trenk


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.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-12.ps.gz
DIMACS Home Page