On tractable cases of Target Set Selection

Abrahamson KA, Downey RG, Fellows MR (1995) Fixed-parameter tractability and completeness IV: on completeness for W[P] and PSPACE analogues. Ann Pure Appl Logic 73(3):235–276

Ackerman E, Ben-Zwi O, Wolfovitz G (2010) Combinatorial model and bounds for target set selection. Theor Comput Sci 411(44–46):4017–4022

Agarwal N, Liu H, Tang L, Yu P (2011) Modeling blogger influence in a community. Soc Netw Anal Min (to appear)

Bazgan C, Chopin M, Fellows MR (2011) Parameterized complexity of the firefighter problem. In: Proceedings of 22nd ISAAC, LNCS, vol 7074. Springer, Berlin, pp 643–652

Ben-Zwi O, Hermelin D, Lokshtanov D, Newman I (2011) Treewidth governs the complexity of target set selection. Discrete Optim 8(1):87–96

Böcker S (2011) A golden ratio parameterized algorithm for cluster editing. In: Proceedings of 22nd IWOCA, LNCS, vol 7056. Springer, Berlin, pp 85–95

Böcker S, Damaschke P (2011) Even faster parameterized cluster deletion and cluster editing. Inf Process Lett 111(14):717–721

Bodlaender HL (2009) Kernelization: New upper and lower bound techniques. In: Proceedings of 4th IWPEC, LNCS, vol 5917. Springer, Berlin, pp 17–37

Bodlaender HL, Jansen BMP, Kratsch S (2011a) Preprocessing for treewidth: A combinatorial analysis through kernelization. In: Proceedings of 38th ICALP, LNCS, vol 6755. Springer, Berlin, pp 437–448

Bodlaender HL, Thomassé S, Yeo A (2011b) Kernel bounds for disjoint cycles and disjoint paths. Theor Comput Sci 412(35):4570–4578

Brandstädt A, Le VB, Spinrad JP (1999) Graph classes: a survey. SIAM Monographs on Discrete Mathematics and Applications, vol 3. SIAM, Auckland

Chen J, Kanj IA, Xia G (2010) Improved upper bounds for vertex cover. Theor Comput Sci 411(40–42):3736–3756

Chen N (2009) On the approximability of influence in social networks. SIAM J Discrete Math 23(3):1400–1415

Cygan M, Fomin F, Leeuwen EJV (2012) Parameterized complexity of firefighting revisited. In: Proceedings of 6th IPEC, LNCS, vol 7112. Springer, Berlin, pp 13–26

Davidson SB, Garcia-Molina H, Skeen D (1985) Consistency in partitioned networks. ACM Comput Surv 17(3):341–370

De Nooy W, Mrvar A, Batagelj V (2011) Exploratory social network analysis with Pajek. No. 34 in structural analysis in the social sciences. Cambridge University Press, Cambridge

Dom M, Lokshtanov D, Saurabh S (2009) Incompressibility through colors and IDs. In: Proceedings of 36th ICALP, LNCS, vol 5555. Springer, Berlin, pp 378–389

Domingos P, Richardson M (2001) Mining the network value of customers. In: Proceedings of 7th ACM KDD. ACM Press, New York, pp 57–66

Downey R, Fellows M, McCartin C, Rosamond F (2008) Parameterized approximation of dominating set problems. Inf Process Lett 109(1):68–70

Downey RG, Fellows MR (1999) Parameterized complexity. Springer, Berlin

Dreyer PA Jr, Roberts FS (2009) Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion. Discrete Appl Math 157:1615–1627

Easley D, Kleinberg J (2010) Networks, crowds, and markets: reasoning about a highly connected world. Cambridge University Press, Cambridge

Fellows M (2009) Towards fully multivariate algorithmics: some new results and directions in parameter ecology. In: Proceedings of 20th IWOCA, LNCS, vol 5874. Springer, Berlin, pp 2–10

Fellows MR, Lokshtanov D, Misra N, Rosamond FA, Saurabh S (2008) Graph layout problems parameterized by vertex cover. In: Proceedings of 19th ISAAC, LNCS, vol 5369. Springer, Berlin, pp 294–305

Fiala J, Golovach PA, Kratochvíl J (2011) Parameterized complexity of coloring problems: treewidth versus vertex cover. Theor Comput Sci 412(23):2513–2523

Flum J, Grohe M (2006) Parameterized complexity theory. Springer, Berlin

Franks DW, Noble J, Kaufmann P, Stagl S (2008) Extremism propagation in social networks with hubs. Adapt Behav 16(4):264–274

Garcia-Molina H, Barbará D (1985) How to assign votes in a distributed system. J ACM 32(4):841–860

Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, Gordonsville

Girvan M, Newman MEJ (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99(12):7821–7826

Guo J, Niedermeier R (2007) Invitation to data reduction and problem kernelization. ACM SIGACT News 38(1):31–45

Harant J, Pruchnewski A, Voigt M (1999) On dominating sets and independent sets of graphs. Comb Probab Comput 8(6):547–553

Jiang H, Zhang C, Zhu B (2010) Weak kernels. Tech. Rep. TR10-005, Department of Computer Science, Montana State University

Johnson DS (1984) The genealogy of theoretical computer science: a preliminary report. SIGACT News 16(2):36–49, reprinted in Bulletin of the EATCS, No. 25, pp 198–211, 1985

Jurvetson S (2000) What exactly is viral marketing? Red Herring 78:110–112

Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. In: Proceedings of 9th ACM KDD. ACM Press, New York, pp 137–146

Kutten S, Peleg D (1999) Fault-local distributed mending. J Algorithms 30(1):144–165

Leskovec J, Horvitz E (2008) Planetary-scale views on a large instant-messaging network. In: Proceedings of 17th WWW. ACM Press, New York, pp 915–924

Leskovec J, Adamic LA, Huberman BA (2007a) The dynamics of viral marketing. ACM Trans Web 1(1)

Leskovec J, McGlohon M, Faloutsos C, Glance NS, Hurst M (2007b) Patterns of cascading behavior in large blog graphs. In: Proceedings of 7th SDM. SIAM, Auckland, pp 551–556

MacGillivray G, Wang P (2003) On the firefighter problem. J Comb Math Comb Comput 47:83–96

McConnell RM, Spinrad J (1994) Linear-time modular decomposition and efficient transitive orientation of comparability graphs. In: Proceedings of 5th SODA. ACM/SIAM, New York, pp 536–545

Milgram S (1967) The small world problem. Psychol Today 1:61–67

Newman MEJ (2003) The structure and function of complex networks. SIAM Rev 45(2):167–256

Newman MEJ (2010) Networks: an introduction. Oxford University Press, Oxford

Newman MEJ, Park J (2003) Why social networks are different from other types of networks. Phys Rev E 68(3):036122

Niedermeier R (2006) Invitation to fixed-parameter algorithms. Oxford University Press, Oxford

Niedermeier R (2010) Reflections on multivariate algorithmics and problem parameterization. In: Proceedings of 27th STACS, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, LIPIcs, vol 5, pp 17–32

Norlen K, Lucas G, Gebbie M, Chuang J (2002) Eva: extraction, visualization and analysis of the telecommunications and media ownership network. In: Proceedings of 14th ITS

Pelc A (1996) Efficient fault location with small risk. In: SIROCCO, Carleton Scientific, pp 292–300

Peleg D (2002) Local majorities, coalitions and monopolies in graphs: a review. Theor Comput Sci 282:231–257

Potterat JJ, Phillips-Plummer L, Muth SQ, Rothenberg RB, Woodhouse DE, Maldonado-Long TS, Zimmerman HP, Muth JB (2002) Risk network structure in the early epidemic phase of HIV transmission in Colorado Springs. Sex Transm Infect 78:159–163

Raeder T, Chawla N (2011) Market basket analysis with networks. Soc Netw Anal Min 1:97–113

Richardson M, Domingos P (2002) Mining knowledge-sharing sites for viral marketing. In: Proceedings of 8th ACM KDD. ACM Press, New York, pp 61–70

Shamir R, Sharan R, Tsur D (2004) Cluster graph modification problems. Discrete Appl Math 144(1–2):173–182

Tarjan RE (1974) A note on finding the bridges of a graph. Inf Process Lett 2(6):160–161

Uhlmann J, Weller M (2010) Two-layer planarization parameterized by feedback edge set. In: Proceedings of 7th TAMC, LNCS, vol 6108, Springer, Berlin, pp 431–442

Wang P, Moeller SA (2002) Fire control on graphs. J Comb Math Comb Comput 41:19–34

Watts D, Peretti J, Frumin M (2007) Viral marketing for the real world. Harv Bus Rev 85(5):22–23

Zhang W, Wu W, Wang F, Xu K (2012) Positive influence dominating sets in power-law graphs. Soc Netw Anal Min 2(1):31–37