Detailansicht
The Target Set Selection Problem with Arbitrary Edge Weights
Ludwig Michael Müller
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Internationale Betriebswirtschaft
Betreuer*in
Markus Leitner
Mitbetreuer*in
Mario Ruthmair
DOI
10.25365/thesis.54109
URN
urn:nbn:at:at-ubw:1-13560.68595.797758-9
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Diese Masterarbeit erörtert, warum das Target Set Selection Problem (TSSP) für Forschungsfelder, die an Bedeutung zunehmen, von
großer Wichtigkeit ist. Der Einfluss von Eigenschaften von Graphen
auf die Komplexität der Lösung des TSSP wird gezeigt. Für den
Fall von Graphen mit beliebigen Kantengewichten wird eine neue
Formulierung der ganzzahligen linearen Optimierung eingeführt und
gezeigt, wo die Tücken beim Finden eines Target Sets im Falle von
Graphen mit beliebigen Kantengewichten sind. Für Instanzen mit unterschiedlichen strukturellen Eigenschaften, sowie für reale Datensätze,
wurden Lösungen des TSSP gefunden und analysiert. Eine Erkennt-
nis ist, dass eine hohe Dichte des Graphen, mehr noch als die Anzahl
der Knoten, zu einer hohen Rechenzeit zur Ermittlung der Lösung des
TSSP führt.
Abstract
(Englisch)
This master’s thesis reasons why the Target Set Selection Problem
(TSSP) is of high relevance to research topics of gaining importance.
The impact of graph properties on the complexity of solving the TSSP
is shown. For the case of graphs with arbitrary edge weights, a novel
integer linear programming formulation is established, and it is shown
where the pitfalls of finding target sets in graphs with arbitrary edge
weights are. For instances with different structural features, as well as
for real-world data, solutions have been found and analyzed. One of
the findings is, that even more than the number of nodes, a high graph
density leads to a great increase in calculation time for determining
the solution of the TSSP.
Schlagwörter
Schlagwörter
(Englisch)
Target Set Selection Arbitrary Edge Weights
Schlagwörter
(Deutsch)
Target Set Selection Arbitrary Edge Weights
Autor*innen
Ludwig Michael Müller
Haupttitel (Englisch)
The Target Set Selection Problem with Arbitrary Edge Weights
Paralleltitel (Deutsch)
Das Target Set Selection Problem mit beliebigen Kantengewichten
Publikationsjahr
2018
Umfangsangabe
ii, 51 Seiten : Diagramme
Sprache
Englisch
Beurteiler*in
Markus Leitner
Klassifikationen
31 Mathematik > 31.80 Angewandte Mathematik ,
85 Betriebswirtschaft > 85.40 Marketing
AC Nummer
AC15180640
Utheses ID
47811
Studienkennzahl
UA | 066 | 914 | |