Computing the dimension of N-free ordered sets is NP-complete

Henry Kierstead; S. G. Penrice

doi:10.1007/BF02034331

Computing the dimension of N-free ordered sets is NP-complete

Henry Kierstead, S. G. Penrice

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

We show that the problem of deciding whether an N-free ordered set has dimension at most 3 is NP-complete.

Original language	English (US)
Pages (from-to)	133-135
Number of pages	3
Journal	Order
Volume	6
Issue number	2
DOIs	https://doi.org/10.1007/BF02034331
State	Published - Jun 1 1989

Keywords

AMS subject classification (1980): 06A10.
N-free
NP-complete
Ordered set
dimension

ASJC Scopus subject areas

Algebra and Number Theory
Geometry and Topology
Computational Theory and Mathematics

Access to Document

10.1007/BF02034331

Cite this

@article{33df1a8b9a3846f4922f8637fa18852b,

title = "Computing the dimension of N-free ordered sets is NP-complete",

abstract = "We show that the problem of deciding whether an N-free ordered set has dimension at most 3 is NP-complete.",

keywords = "AMS subject classification (1980): 06A10., N-free, NP-complete, Ordered set, dimension",

author = "Henry Kierstead and Penrice, {S. G.}",

year = "1989",

month = jun,

day = "1",

doi = "10.1007/BF02034331",

language = "English (US)",

volume = "6",

pages = "133--135",

journal = "Order",

issn = "0167-8094",

publisher = "Springer Netherlands",

number = "2",

}

TY - JOUR

T1 - Computing the dimension of N-free ordered sets is NP-complete

AU - Kierstead, Henry

AU - Penrice, S. G.

PY - 1989/6/1

Y1 - 1989/6/1

N2 - We show that the problem of deciding whether an N-free ordered set has dimension at most 3 is NP-complete.

AB - We show that the problem of deciding whether an N-free ordered set has dimension at most 3 is NP-complete.

KW - AMS subject classification (1980): 06A10.

KW - N-free

KW - NP-complete

KW - Ordered set

KW - dimension

UR - http://www.scopus.com/inward/record.url?scp=34249973232&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34249973232&partnerID=8YFLogxK

U2 - 10.1007/BF02034331

DO - 10.1007/BF02034331

M3 - Article

AN - SCOPUS:34249973232

SN - 0167-8094

VL - 6

SP - 133

EP - 135

JO - Order

JF - Order

IS - 2

ER -

Computing the dimension of N-free ordered sets is NP-complete

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this