Seitz, G. (2009). Parking functions and generalizations [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-23417
E104 - Institut für Diskrete Mathematik und Geometrie
-
Date (published):
2009
-
Number of Pages:
92
-
Keywords:
Parkfunktionen; diskrete Mathematik
de
parking functions; discrete mathematics
en
Abstract:
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
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 />