Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
Die vorliegende Dissertation behandelt kombinatorische Optimierungsprobleme, die mit dem Erweitern von Websites durch zusätzliche Hyperlinks zusammenhängen. Das Einfügen ggf. speziell hervorgehobener zusätzlicher Links, so genannter Hotlinks, ist ein Verfahren zur Optimierung von Websites. Ein Vorteil dieses Verfahrens ist, dass es nicht destruktiv ist, da die ursprüngliche Struktur der Site erhalten bleibt. Hotlinks können - abhängig von den Interessen der Benutzer - so zugeordnet werden, dass auf beliebtere Seiten schneller zugegriffen werden kann. Auf diese Weise wird die erwartete Anzahl an ,,Klicks minimiert und der Datenverkehr gleichzeitig verringert. Eine hierarchisch aufgebaute Website kann formal als gewichteter Baum T = (V,E,omega) beschrieben werden, wobei (V,E) ein Baum mit Wurzel r ist. Die Gewichtsfunktion omega ordnet jedem Knoten eine Zugriffswahrscheinlichkeit zu. Ein Hotlink Assignment ist eine Menge A von zusätzlichen Kanten, welche für die Benutzer Abkürzungen darstellen. Aus Gründen der Übersichtlichkeit ist nur eine gewisse Anzahl ausgehender Hotlinks pro Seite erlaubt. Ein Hotlink Assignment ist für einen gegebenen gewichteten Baum optimal, wenn es unter allen zulässigen Assignments die erwartete Länge des Pfades von der Wurzel r zu einem Knoten im Baum minimiert. Hierbei betrachten wir nicht den kürzesten Pfad, sondern gehen davon aus, dass jeder Hotlink auf dem Weg von der Wurzel zum Zielknoten durch die Benutzerin oder den Benutzer unmittelbar benutzt wird. Nach einer ausführlichen Einführung in die Problemstellung befassen wir uns zunächst mit der Berechnungskomplexität der optimalen Lösung. Hierbei zeigen wir, dass es NP-vollständig ist, zu entscheiden, ob für einen gegebenen Baum ein Hotlink Assignment existiert, welches eine bestimmte erwartete Pfadlänge erreicht. Dies gilt selbst für den Fall, dass maximal ein Hotlink von jedem Knoten ausgehen darf und dass nur die Blätter positive Zugriffswahrscheinlichkeit haben. Im darauffolgenden Kapitel identifizieren wir eine praxisrelevante ...