No label defined (Q4409148)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1942448
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1942448 |
Statements
30 June 2003
0 references
separation
0 references
0.9056207
0 references
0.88385683
0 references
0 references
0.86764866
0 references
0.8657583
0 references
Zusammenfassung und Ausblick: Für Bäume, kreisfreie Graphen und Graphen, für die innerhalb jeder 2-Zusammenhangskomponente die Online-Entfernungsberechnung in konstanter Laufzeit möglich ist, haben wir in Kapitel 5 optimale Werte für \({\mathcal S}\), \({\mathcal T}\) und \({\mathcal Q}\) gezeigt, d.h. eine lineare Preprocessing-Phase genügt, um SPSD in konstanter Laufzeit zu berechnen. In den Kapiteln 6 und 7 haben wir zwei konträre Ansätze zur Konstruktion Hierarchischer Graphen untersucht. Geeignete Knotenmenge wie auch die Separatormengen sollten möglichst klein sein, jedoch separieren Geeignete Knotenmengen den Graphen i. A. nicht, und Separatormengen sind i. A. keine Geeigneten Knotenmengen. Die Berechnung minimaler Geeigneter Knotenmengen und die Berechnung minimaler Umgebungsabstände haben wir als NP-vollständig nachgewiesen und eine logarithmische bzw. konstante Approximation (für den Umgebungsabstand) angegeben. Außerdem haben wir eine Verallgemeinerung Geeigneter Graphen zu teilgeeigneten Graphen definiert und das Eignungskonzept auf Levelgraphen übertragen. In Kapitel 7 haben wir ein rekursives Separationskonzept -- Separatorbäume -- eingeführt und darauf verschiedene Hierarchische Graphen definiert. Sofern nur ein \(\alpha\)-\(\beta\)-\(f(n)\)-Separatorbaum zur Verfügung steht, haben wir \({\mathcal S}\in O(n(f(n)+\log n))\), \({\mathcal T}\in O((m+ n\log n)f(n))\) und \({\mathcal Q}\in O(f(n))\) nachgewiesen. Aus den Separatorbäumen haben wir die Separatorweite als einen neuen charakteristischen Parameter eines Graphen abgeleitet und gezeigt, dass sie i. A. von der Baumweite verschieden ist und höchstens um einen logarithmischen Faktor von der Baumweite abweicht. Hier ist die These naheliegend, dass einige i.A. NP-vollständige Probleme für Graphen mit konstanter Separatorweite ebenso wie für Graphen mit konstanter Baumweite in \(P\) liegen. Dies ist noch zu prüfen. Für planare Graphen konnten wir mittels sogenannter Dünner-Trennender-Hierarchischer-Graphen zeigen, dass fast ein linearer Speicherplatz genügt, um \({\mathcal Q}\in\widetilde O(\sqrt{n})\) zu gewährleisten. Das Konzept der Separation eignet sich auch für Approximationen. Für beliebige Graphen kann auf fast linearem Platz ein Einfacher-Trennender-Hierarchischer-Graph berechnet werden, so dass online die Entfernung in fast konstanter Laufzeit approximiert wird. Für beide untersuchten Ansätze zur Konstruktion Hierarchischer Graphen haben sich weitere Fragestellungen ergeben. Für Geeignete Graphen sollte insbesondere das Kriterium für die Umgebungsgröße variiert werden. Um dabei auch konkrete Werte für \({\mathcal S}\), \({\mathcal T}\) und \({\mathcal Q}\) in der \(O\)-Notation zu erhalten, muss das Eignungskonzept auf spezielle Graphklassen, ähnlich den \(k\)-Levelgittergraphen in Abschnitt 6.6.1, angewendet werden. Der Ansatz der rekursiven Separation lässt sich eventuell dadurch verbessern, dass man Separationen nur bezüglich der kürzesten Wege betrachtet, d.h. man ändert in der Definition 10 die Gleichung 7.1 zu: \[ \forall_{u\in X_1} \forall_{v\in X_2} \forall_{w\in SP(u,v)}\qquad V(w)\cap Y\neq\emptyset. \] Hier benötigt man dann ein neues Separationsverfahren ähnlich dem von Lipton und Tarjan, das wir in dieser Arbeit benutzt haben. Interessant ist außerdem, ob sich das Konzept der DTHG auch auf andere nichtplanare Graphen adaptieren lässt. Kombinationen der beiden Hierarchiekonzepte und die Angemessenheit, um dynamische Aspekte von Graphen abzubilden, sollten ebenfalls künftig untersucht werden. Insbesondere im Zusammenhang mit Verkehrsinformationssystemen besteht hier ein großer Bedarf. Aus theoretischer Sicht sind die unteren Schranken für die Parameter \({\mathcal S}\), \({\mathcal T}\) und \({\mathcal Q}\) i. A. und abhängig von den gegebenen Graphen zu untersuchen. Einen Hinweis liefert hier das Resultat \({\mathcal S}{\mathcal Q}\in\widetilde O(n^{1.5})\) für planare Graphen, das modulo logarithmischer Faktoren optimal ist.
0 references