Objekt-Metadaten

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

HaupttitelOn the complexity of partial order properties
AutorFelsner, Stefan
AutorWagner, Dorothea
Institution/KörperschaftUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
Seitenzahl13 S.
Schriftenreihe [Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; 1999,19]
DDC510 Mathematik
ZusammenfassungThe 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.
Dokumente
pdf-Datei
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
 
Fachbereich/EinrichtungFB Mathematik und Informatik
Arbeitsbereich/InstitutInstitut für Informatik
Erscheinungsjahr1999
Dokumententyp/-SammlungenKarten
SpracheEnglisch
Rechte Nutzungsbedingungen
Erstellt am22.10.2009 - 12:18:56
Letzte Änderung23.01.2014 - 16:21:35
 
Statische URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000004025
Zugriffsstatistik
 

LOADING...