On the complexity of partial order properties
Felsner, Stefan ;  Wagner, Dorothea ;  Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik

Main titleOn the complexity of partial order properties
AuthorFelsner, Stefan
AuthorWagner, Dorothea
InstitutionUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
No. of Pages13 S.
Series [Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; 1999,19]
Classification (DDC)510 Mathematics
AbstractThe recognition complexity of ordered set properties is considered, i.e. how many questions have to be asked to decide if an unknown ordered set has a prescribed property. We prove a lower bound of Ω (n²) for properties that are characterized by forbidden substructures of fixed size. For the properties being connected, and having exactly k comparable paris we show that the recogintion complexity is (n:2); the complexity of interval orders is exactly (n:2) -1. Non-trivial upper bounds are given for being a lattice, containing a chain of length k ≥ 2 and having width k.
If your browser can't open the file, please download the file first and then open it
FU DepartmentDepartment of Mathematics and Computer Science
Other affiliation(s)Institut für Informatik
Year of publication1999
Type of documentWorking paper
Terms of use/Rights Nutzungsbedingungen
Created at2009-10-22 : 12:18:56
Last changed2015-03-06 : 10:46:11
Static URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000004025