DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click HERE
to register or log in.
A CHARACTERIZATION OF COMPARABILITY GRAPHS AND OF INTERVAL GRAPHS
IBM WATSON RESEARCH CENTER YORKTOWN HEIGHTS N Y
ALTHOUGH PARTIAL ORDERING IS AN ASYMMETRIC RELATION, COMPARABILITY IN A PRTIALY ODERED SET IS SYMMETRIC. Symmetric relations on a set which are comparability relations in some partial ordering of the elements of the set are presented. As an application, a well-know problem of Hajos, to characterize the relation of overlapping among an arbitrary family of intervals of a simply ordered set, is also solved. For both characterization problems, appropriate algorithms are proposed. Author