Some Results on the Target Set Selection Problem

Details Some Results on the Target Set Selection Problem Some Results on the Target Set Selection Problem

2011-11-29

arxiv.org/abs/1111.6685v1

Mathematics

Combinatorics

Scientific paper

In this paper we consider a fundamental problem in the area of viral marketing, called T{\scriptsize ARGET} S{\scriptsize ET} S{\scriptsize ELECTION} problem. We study the problem when the underlying graph is a block-cactus graph, a chordal graph or a Hamming graph. We show that if $G$ is a block-cactus graph, then the T{\scriptsize ARGET} S{\scriptsize ET} S{\scriptsize ELECTION} problem can be solved in linear time, which generalizes Chen's result \cite{chen2009} for trees, and the time complexity is much better than the algorithm in \cite{treewidth} (for bounded treewidth graphs) when restricted to block-cactus graphs. We show that if the underlying graph $G$ is a chordal graph with thresholds $\theta(v)\leq 2$ for each vertex $v$ in $G$, then the problem can be solved in linear time. For a Hamming graph $G$ having thresholds $\theta(v)=2$ for each vertex $v$ of $G$, we precisely determine an optimal target set $S$ for $(G,\theta)$. These results partially answer an open problem raised by Dreyer and Roberts \cite{Dreyer2009}.

Affiliated with

Also associated with

No associations

Rating

Some Results on the Target Set Selection Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Some Results on the Target Set Selection Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Some Results on the Target Set Selection Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-14774