Bibliography | Buchholz, Friedhelm: Komplexität des Fahrgemeinschaften-Problems. University of Stuttgart, Faculty of Computer Science, Student Thesis No. 1327 (1994). 70 pages, german.
|
CR-Schema | F.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)
|
Keywords | Reduktion ; 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 date | September 10, 1996 |
---|