History


Help on query formulation
Target set selection in social networks. (Zielgruppenauswahl in sozialen Netzwerken.) (German)
Wurzel 45, No. 3-4, 54-61 (2011).
Aus der Einleitung: Zielgruppenauswahl ist ein $NP$-vollständiges Problem. Demnach geht man davon aus (falls $P\ne NP$), dass es keinen effizienten Algorithmus gibt, der für alle möglichen sozialen Netzwerke in Polynomialzeit die Frage beantwortet, wem man zu Anfang von der Information erzählen sollte. Ein soziales Netzwerk kann als Graph modelliert werden. In diesem Artikel werden für vollständige Graphen Algorithmen für Probleme der Zielgruppenauswahl behandelt, die lineare oder quasi-lineare Laufzeit haben. Quasi-linear bedeutet, dass ein Algorithmus in $O(n log n)$ läuft.
From the introduction (translation): Target group selection is a $NP$-complete problem. Therefore, one assumes (if $P\ne NP$) that there is no efficient algorithm that can answer for every possible social network in polynomial time the question which person has to be informed at first. A social network can be modelled as a graph. For complete graphs, this article treats algorithms for problems of target group selection that have a linear or quasi-linear run-time. Quasi-linear means that an algorithm runs in $O(n log n)$.
Classification: P20 N70 K30
Valid XHTML 1.0 Transitional Valid CSS!