Objekt-Metadaten
On the complexity of partial order properties Felsner, Stefan ; Wagner, Dorothea ; Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik |
Main title | On the complexity of partial order properties |
Author | Felsner, Stefan |
Author | Wagner, Dorothea |
Institution | Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik |
No. of Pages | 13 S. |
Series | [Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; 1999,19] |
Classification (DDC) | 510 Mathematics |
Abstract | The 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. |
Documents |
pdf-Datei
If your browser can't open the file, please download the file first and then open it
|
FU Department | Department of Mathematics and Computer Science |
Other affiliation(s) | Institut für Informatik |
Year of publication | 1999 |
Type of document | Working paper |
Language | English |
Terms of use/Rights | Nutzungsbedingungen |
Created at | 2009-10-22 : 12:18:56 |
Last changed | 2015-03-06 : 10:46:11 |
Static URL | http://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000004025 |
Statistics | |