Journal of Computer Science
and Information Technology

On Hybrid Order Dimensions
Athanasios Andrikopoulos

Abstract
Norbert Wiener [28] developed the concept of interval order to clarify the link between the notions of a time instant and a time period. This was a problem on which Bertrand Russell [18] was working at the time. Interval orders are especially essential in the study of linear-interval and linear-semiorderdimensions. This kind of dimensions, which we refer to as hybrid order dimensions, provides a common generalization of linear order and interval order (semiorder) dimension and is arguably the most important measure of the complexity of ordered sets. As a result, they play a significant role in a wide range of areas of pure and applied mathematics, graph theory, computer science, and engineering. In this paper, we give three main results of the theory of hybrid order dimensions. More precisely, we obtain necessary and sufficient conditions for a binary relation to have an interval order (resp. linear- interval order, linear-simiorder) extension as well as a realizer of interval orders (resp. linear-interval orders, linear-simiorders). In addition, we characterize the interval order (respectively linear-interval order, linear-simiorder) dimension. Since the hybrid order dimension of a binary relation is less than its linear order dimension, these results will allow for the development of more efficient algorithms in graph theory and computer science.

Full Text: PDF     DOI: 10.15640/jcsit.v9n2a2