On the Complexity of Partial Order Properties

by: Stefan Felsner, Ravi Kant, Pandu C Rangan, Dorothea Wagner

Order, Vol. 17, No. 2. (1 June 2000), pp. 179-193.

View FullText article

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

AbnerCYH

Find related articles with these CiteULike tags

combinatorics, complexity, order, testing, topology

Abstract

The recognition complexity of ordered set properties is considered in terms of how many questions must be put to an adversary to decide if an unknown partial order has the prescribed property. We prove a lower bound of order n2 for properties that are characterized by forbidden substructures of fixed size. For the properties being connected, and having exactly k comparable pairs, k = n2 / 4 we show that the recognition complexity is (n\choose 2). The complexity of interval orders is exactly (n\choose 2) - 1. We further establish bounds for being a lattice, being of height k and having width k.

@article{citeulike:1808784, abstract = {The recognition complexity of ordered set properties is considered in terms of how many questions must be put to an adversary to decide if an unknown partial order has the prescribed property. We prove a lower bound of order n2 for properties that are characterized by forbidden substructures of fixed size. For the properties being connected, and having exactly k comparable pairs, k = n2 / 4 we show that the recognition complexity is (n\choose 2). The complexity of interval orders is exactly (n\choose 2) - 1. We further establish bounds for being a lattice, being of height k and having width k.}, author = {Felsner, Stefan and Kant, Ravi and Rangan, Pandu C. and Wagner, Dorothea }, citeulike-article-id = {1808784}, doi = {10.1023/A:1006422023869}, journal = {Order}, keywords = {combinatorics, complexity, order, testing, topology}, month = {June}, number = {2}, pages = {179--193}, posted-at = {2007-10-23 04:27:47}, priority = {2}, title = {On the Complexity of Partial Order Properties}, url = {http://dx.doi.org/10.1023/A:1006422023869}, volume = {17}, year = {2000} }

RIS record

TY - JOUR ID - citeulike:1808784 L3 - citeulike-article-id:1808784 TI - On the Complexity of Partial Order Properties JF - Order VL - 17 IS - 2 SP - 179 EP - 193 N2 - The recognition complexity of ordered set properties is considered in terms of how many questions must be put to an adversary to decide if an unknown partial order has the prescribed property. We prove a lower bound of order n2 for properties that are characterized by forbidden substructures of fixed size. For the properties being connected, and having exactly k comparable pairs, k = n2 / 4 we show that the recognition complexity is (n\choose 2). The complexity of interval orders is exactly (n\choose 2) - 1. We further establish bounds for being a lattice, being of height k and having width k. KW - combinatorics KW - complexity KW - order KW - testing KW - topology AU - Felsner, Stefan AU - Kant, Ravi AU - Rangan, Pandu AU - Wagner, Dorothea PY - 2000/06/01/ UR - http://dx.doi.org/10.1023/A:1006422023869 ER -

RIS BibTeX