Student Thesis STUD-1327

BibliographyBuchholz, Friedhelm: Komplexität des Fahrgemeinschaften-Problems.
University of Stuttgart, Faculty of Computer Science, Student Thesis No. 1327 (1994).
70 pages, german.
CR-SchemaF.1.3 (Complexity Classes)
F.2.0 (Analysis of Algorithms and Problem Complexity General)
F.2.2 (Nonnumerical Algorithms and Problems)
G.2.2 (Graph Theory)
KeywordsReduktion ; NP-hart ; NP-vollständig ; Effizient ; Graph ; Partition
Abstract

In dem OFFIS Projekt Fahrgemeinschaften (Oldenburger Forschung- und Entwicklungsinstitut Für Informatik-Werkzeuge und -Systeme) hat sich gezeigt, daß die Einteilung einer gegebenen Personenmenge in Fahrgemeinschaften unter der Optimierung einer Zielfunktion äußerst schwierig sein kann. Im allgemeinen soll die Anzahl der Fahrgemeinschaften minimiert werden, wobei keine Fahrgemeinschaft eine bestimmte Umwegschranke (Zeit oder Weglänge) überschreiten darf. Wir haben diese Problemstellung und einige Abwandlungen formalisiert und die Problemkomplexität bestimmt. Wenn nur 2-er Fahrgemeinschaften zugelassen sind, lassen sich die Probleme effizient lösen. Dazu wird der Algorithmus zur Konstruktion eines maximalen Matchings eines Graphen verwendet. Bereits für 3-er Fahrgemeinschaften werden die Probleme NP-hart, auch wenn Nebenbedingungen an die zugrundeliegenden Straßengraphen gestellt werden. In den Reduktionen beziehen wir uns auf folgende Probleme: 3-dimensionales Matching, Exact Cover und Euklidischer Traveling Salesman. Offen geblieben ist, ob sich das Fahrgemeinschafts-Problem effizient lösen läßt, wenn die Start- und Zielorte aller Personen auf einer Geraden liegen

Full text and
other links
PostScript (585403 Bytes)
Access to students' publications restricted to the faculty due to current privacy regulations
Department(s)University of Stuttgart, Institute of Computer Science, Formal Concepts
Entry dateSeptember 10, 1996
   Publ. Computer Science