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 条

[11] HABIB M, 1990, MINIMAL INTERVAL EXT
[12] HABIB M, 1990, RECOGNITION PARTIAL
[13] UPPER BOUND ON DIMENSION OF INTERVAL ORDERS
RABINOVITCH, I
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 1978, 25 (01) : 68 - 71
[14] SPINRAD J, 1983, RECOGNITION ISOMORPH
[15] Trotter W. T. Jr., 1976, Discrete Mathematics, V16, P71, DOI 10.1016/0012-365X(76)90095-9
[16] CHARACTERIZATION PROBLEMS FOR GRAPHS, PARTIALLY ORDERED SETS, LATTICES, AND FAMILIES OF SETS
TROTTER, WT
MOORE, JI
[J]. DISCRETE MATHEMATICS, 1976, 16 (04) : 361 - 381
[17] MAXIMAL DIMENSIONAL PARTIALLY ORDERED SETS .3. CHARACTERIZATION OF HIRAGUCHIS INEQUALITY FOR INTERVAL DIMENSION
TROTTER, WT
BOGART, KP
[J]. DISCRETE MATHEMATICS, 1976, 15 (04) : 389 - 400
[18] WILLE R, 1989, ALGORITHMS ORDER, P33
[19] THE COMPLEXITY OF THE PARTIAL ORDER DIMENSION PROBLEM
YANNAKAKIS, M
[J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1982, 3 (03): : 351 - 358

← 1 2 →