Universität Stuttgart

Permanent URI for this communityhttps://elib.uni-stuttgart.de/handle/11682/1

Browse

Filters

20003

Settings

Subject: search.filters.subject.004Start date: 2000End date: 2000Institute: search.filters.UBSInstitut.Institut für Formale Methoden der Informatik

Search Results

Now showing 1 - 3 of 3
  • Thumbnail Image
    ItemOpen Access
    Gleichungen mit regulären Randbedingungen über freien Gruppen
    (2000) Hagenah, Christian; Diekert, Volker (Prof. Dr.)
    Wir beweisen, daß das Erfüllbarkeitsproblem für Gleichungen mit regulären Randbedingungen über freien Gruppen PSPACE-vollständig ist. Wir zeigen auch, daß eine minimale Lösung einer solchen Gleichung höchstens eine doppelt exponentielle Länge hat und in 2-DEXPTIME berechnet werden kann. Wir reduzieren zuerst das Problem Gleichungen mit regulären Randbedingungen über einer freien Gruppen zu lösen auf das Problem Gleichungen mit regulären Randbedingungen über freien Monoiden mit einer Anti-Involution zu lösen. Anschließend stellen wir einen Algorithmus vor, der in PSPACE entscheidet, ob diese Gleichungen lösbar sind und einen Algorithmus, der in 2-DEXPTIME eine Lösung berechnet, wenn die Gleichung lösbar ist.
  • Thumbnail Image
    ItemOpen Access
    Hierarchische Graphen zur Wegesuche
    (2000) Buchholz, Friedhelm; Claus, Volker (Prof. Dr.)
    In dieser Arbeit wird ein Zwei-Phasenmodell zur effizienten Entfernungsberechnung in gewichteten Graphen untersucht. Bekannte Anwendungsgebiete sind Verkehrsinformationssyteme, VLSI Design, Verteiltes Rechnen und geometrische und parallele Algorithmen. In einer Preprocessing-Phase wird zu einem Graphen ein Hierarchischer Graph (HG) konstruiert, der in der Online-Phase zur Entfernungsberechnung eingesetzt wird. Es werden die Laufzeit (T) der Preprocessing-Phase, die Groesse (S) des HG'en und die Laufzeit (Q) der Online-Phase untersucht. Zwei kontraere Modellierungsansaetze werden vorgestellt: Geeignete Knoten und ein rekursives Separationskonzept. Das Konzept mit Geeigneten Knoten wird auf Levelgraphen verallgemeinert und es wird gezeigt, dass die Berechnung einer minimalen Geeigneten Knotenmenge NP-vollstaendig ist. Die Approximation bzgl. der Groesse der Geeigneten Knotenmenge kann bis auf einen logarithmischen Faktor und bezueglich des Umgebungsabstands bis auf einen konstanten Faktor in polynomieller Laufzeit durchgefuehrt werden. Im Falle von planaren Graphen wird mittels eines erweiterten Separationskonzepts (Ideen von Lingas 1990 und von Didjev 1996 werden kombiniert) gezeigt, dass HG'en von fast linearer Groesse genuegen, um Q in O(n {1.5} log 3 n) zu gewaehrleisten. Dieses Resultat ist modulo logarithmischer Faktoren optimal. Ausserdem wird ein neuer Parameter 'Separatorweite' fuer Graphen eingefuehrt und es wird konstruktiv gezeigt, dass die Separatorweite unabhaengig von der Baumweite ist, aber hoechstens um einen logarithmischen Faktor von der Baumweite abweicht. Am Beispiel wird gezeigt, dass eine logarithmische Abweichung auftreten kann.
  • Thumbnail Image
    ItemOpen Access
    Erfahrungen mit dem System TROSS beim DRK
    (2000) Buchholz, Friedhelm; Wagner, Frank
    Die Projektgruppe Transportoptimierung hat in einem Jahr (WS~97/98, SS~98) das System 'Transportorganisation für soziale Serviceanbieter' (TROSS) zur Disposition für die Fahrdienste des Deutschen Roten Kreuzes (DRK) Stuttgart erstellt. In den Fakultätsberichten Nr. 1998/10 und 1998/06 wird TROSS im Detail vorgestellt. Weil keine Wartung gewährleistet werden kann und das System auch noch einige Fehler hat, wird TROSS vom DRK nicht bei der täglichen Disposition benutzt. Trotzdem ist das Interesse vom DRK an einer computerunterstützten Planung und Optimierung bei der Organisation der Fahrdienste sehr groß. Aus diesem Grund hat man sich dort intensiv mit TROSS beschäftigt. Die dabei gesammelten Erfahrungen und daraufhin durchgeführten Korrekturen an TROSS werden in diesem Bericht zusammengefasst. Am Ende des Berichts werden dann mögliche Erweiterungen des Systems vorgestellt.