Title: Parking functions and generalizations
Language: English
Authors: Seitz, Georg
Qualification level: Diploma
Keywords: Parkfunktionen; diskrete Mathematik
parking functions; discrete mathematics
Advisor: Panholzer, Alois
Issue Date: 2009
Number of Pages: 92
Qualification level: Diploma
Abstract: 
Betrachte eine Einbahnstraße mit n nummerierten Parkplätzen in einer Reihe.
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.
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.
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.
Parkfunktionen wurden auf verschiedene Arten verallgemeinert, und sie treten in der Analyse von Hashing-Varianten und Sortier-Algorithmen auf.
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.
Anschließend werden bekannte Relationen zwischen Parkfunktionen und azyklis- chen Funktionen bzw. markierten Bäumen sowie eine Beziehung zwischen Parkfunktionen und Warteschlangen behandelt.
Schließlich werden Verallgemeinerungen von Parkfunktionen studiert, unter anderem bucket parking functions, x-parking functions und defective parking functions.

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.
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.
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.
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.
Furthermore, we present known relations between parking functions, acyclic functions and labeled trees and a relation between parking functions and priority queues.
Finally, we study generalizations of parking functions, such as bucket parking functions, x-parking functions und defective parking functions.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-23417
http://hdl.handle.net/20.500.12708/11194
Library ID: AC05040285
Organisation: E104 - Institut für Diskrete Mathematik und Geometrie 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

File Description SizeFormat
Parking functions and generalizations.pdf495.37 kBAdobe PDFThumbnail
 View/Open
Show full item record

Page view(s)

7
checked on Feb 18, 2021

Download(s)

48
checked on Feb 18, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.