A RECOGNITION ALGORITHM FOR ORDERS OF INTERVAL DIMENSION-2

被引：11
作者：
LANGLEY, LJ
机构：
[1] Department of Mathematics, University of Colorado at Denver, Denver, CO 80217-3364, Campus Box 170
来源：
DISCRETE APPLIED MATHEMATICS | 1995年 / 60卷 / 1-3期
关键词：
D O I：
10.1016/0166-218X(94)00056-J
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
From a partially ordered set (X, <) one may construct the collection PS(X) consisting of a collection of subsets of X ordered by inclusion. We show that the interval dimension of X equals the dimension of PS(X) and give an O(n(3)) algorithm to determine whether X has interval dimension less than or equal to 2 and construct an interval realizer of X.
引用
收藏
页码：257 / 266
页数：10
相关论文
共 19 条
  • [1] [Anonymous], 1985, INTERVAL ORDERS INTE
  • [2] BOGART KP, 1991, OBVIOUS PROOF FISHBU
  • [3] BOUCHET A, 1971, THESIS U SCI GRENOBL
  • [4] COGIS O, 1980, THESIS U P M CURIE P
  • [5] COPPERSMITH D, 1987, 19TH P ANN S COMP
  • [6] TRAPEZOID GRAPHS AND THEIR COLORING
    DAGAN, I
    GOLUMBIC, MC
    PINTER, RY
    [J]. DISCRETE APPLIED MATHEMATICS, 1988, 21 (01) : 35 - 46
  • [7] Partially ordered sets
    Dushnik, B
    Miller, EW
    [J]. AMERICAN JOURNAL OF MATHEMATICS, 1941, 63 : 600 - 610
  • [8] Golumbic M. C., 1980, ALGORITHMIC GRAPH TH
  • [9] Greenough T. L, 1976, THESIS DARTMOUTH COL
  • [10] INTERVAL DIMENSION IS A COMPARABILITY INVARIANT
    HABIB, M
    KELLY, D
    MOHRING, RH
    [J]. DISCRETE MATHEMATICS, 1991, 88 (2-3) : 211 - 229
12