Betrachte eine Einbahnstraße mit n nummerierten Parkplätzen in einer Reihe.<br />m aufeinanderfolgende Fahrer wollen in dieser Straße parken, wobei jeder einen bevorzugten Parkplatz hat. Jeder Fahrer fährt zu der gewählten Stelle und parkt dort, falls sie frei ist. Falls nicht, nimmt er den nächsten freien Parkplatz, falls vorhanden. Andernfalls verlässt er die Straße.<br />Die Funktion p : [m] ->[n], die jedem Fahrer i den bevorzugten Parkplatz p(i) zuweist, heißt Parkfunktion (parking function), falls alle m Fahrer erfolgreich parken können.<br />Viele Beziehungen zwischen Parkfunktionen und anderen kombinatorischen Objek- ten wie zum Beispiel markierten Bäumen, azyklischen Funktionen, Warteschlangen, nichtkreuzenden Partitionen und speziellen Polytopen sind bekannt.<br />Parkfunktionen wurden auf verschiedene Arten verallgemeinert, und sie treten in der Analyse von Hashing-Varianten und Sortier-Algorithmen auf.<br />In dieser Arbeit werden einige grundlegende Eigenschaften von Parkfunktionen gesammelt. Es wird gezeigt, wo Parkfunktionen bei der Analyse von Hashtabellen auftreten, und ein neues Resultat über Haltepunkte (breakpoints) von Parkfunktionen wird präsentiert.<br />Anschließend werden bekannte Relationen zwischen Parkfunktionen und azyklis- chen Funktionen bzw. markierten Bäumen sowie eine Beziehung zwischen Parkfunktionen und Warteschlangen behandelt.<br />Schließlich werden Verallgemeinerungen von Parkfunktionen studiert, unter anderem bucket parking functions, x-parking functions und defective parking functions.<br />
de
dc.description.abstract
Consider a one-way street with n numbered parking slots in a line. There are m consecutive drivers who wish to park in this street, each of which has a preferred parking slot in mind. Each driver proceeds to the chosen place and parks there, if it is empty. If not, the driver takes the first available space, if any. If no space is empty, the driver leaves.<br />The function p : [m] ->[n] which associates each driver i with his preferred parking slot p(i) is called a parking function if all drivers are able to park.<br />Many relations between parking functions and other combinatorial objects are known, such as labeled trees, acyclic functions, priority queues, noncrossing partitions and special polytopes. Parking functions have been generalized in various ways, and they appear in the analysis of hashing variants and sorting algorithms.<br />In this work, we collect some basic properties of parking function. We show where they appear in the analysis of hashing with linear probing and then give a new result on breakpoints.<br />Furthermore, we present known relations between parking functions, acyclic functions and labeled trees and a relation between parking functions and priority queues.<br />Finally, we study generalizations of parking functions, such as bucket parking functions, x-parking functions und defective parking functions.<br />
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Parkfunktionen
de
dc.subject
diskrete Mathematik
de
dc.subject
parking functions
en
dc.subject
discrete mathematics
en
dc.title
Parking functions and generalizations
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Georg Seitz
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
tuw.publication.orgunit
E104 - Institut für Diskrete Mathematik und Geometrie