Unit Interval Orders of Open and Closed Intervals |
| |
Authors: | Alan Shuchat Randy Shull Ann N Trenk |
| |
Institution: | 1.Department of Mathematics,Wellesley College,Wellesley,USA;2.Department of Computer Science,Wellesley College,Wellesley,USA |
| |
Abstract: | A poset P = (X, ?) is a unit OC interval order if there exists a representation that assigns an open or closed real interval I(x) of unit length to each x ∈ P so that x ? y in P precisely when each point of I (x) is less than each point in I (y). In this paper we give a forbidden poset characterization of the class of unit OC interval orders and an efficient algorithm for recognizing the class. The algorithm takes a poset P as input and either produces a representation or returns a forbidden poset induced in P. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|