DIMACS TR: 96-12
k-Weak Orders: Recognition and a Tolerance Result
Author: Ann N. Trenk
Abstract:
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