A CHARACTERIZATION OF COMPARABILITY GRAPHS AND OF INTERVAL GRAPHS

Abstract

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)

Document Details

Document Type
Technical Report
Publication Date
Feb 15, 1962
Accession Number
AD0275895

Entities

People

  • A.j. Hoffman
  • P.c. Gilmore

Organizations

  • IBM Thomas J. Watson Research Center

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Intervals

Readers

  • Graph Algorithms and Convex Optimization.