Navigation/Menü: Links auf weitere Seiten dieser Website
Objekt-Metadaten
| On the complexity of partial order properties Felsner, Stefan |
| Haupttitel | On the complexity of partial order properties |
| Autor | Felsner, Stefan; Wagner, Dorothea |
| Seitenzahl | 13 S. |
| Schriftenreihe | [Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; 1999,19] |
| Fachbereich/Einrichtung | FB Mathematik und Informatik |
| Arbeitsbereich/Institut | Institut für Informatik |
| Erscheinungsjahr | 1999 |
| Dokumente | pdf-Datei
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
|
| DDC | 510 Mathematik |
| Dokumententyp/-Sammlungen | Report |
| Medientyp/Format | Text |
| 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. |
| Sprache | Englisch |
| Rechte | Nutzungsbedingungen |
| Zugriffstatistik | |
| Statische URL | http://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000004025 |
| Erstellt am | 22.10.2009 - 14:18:56 |
| Letzte Änderung | 04.04.2013 - 09:33:27 |
