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 | |
