Target set selection on generalized pancake graphs. (English) Zbl 1446.05047
Summary: Target set selection (TSS) was initially proposed to study the problem of the spread of information, ideas or influence through a social network and had formulated many problems arising in various practical applications. We consider a particular type of graphs, namely \(n\)-dimensional \(m\)-sided pancake graph \(mP_n \), which is one class of Cayley graphs and is widely used in the symmetric interconnection networks. We establish a bound of TSS on \(mP_n\) by the minimum feedback vertex set.
MSC:
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 91D30 | Social networks; opinion dynamics |
References:
| [1] | Ackerman, E.; Ben-Zwi, O.; Wolfovitz, G., Combinatorial model and bounds for target set selection, Theoret. Comput. Sci., 411, 4017-4022 (2010) · Zbl 1235.90168 · doi:10.1016/j.tcs.2010.08.021 |
| [2] | Adams, S. S.; Brass, Z.; Stokes, C.; Troxell, D. S., Irreversible k-threshold and majority conversion processes on complete multipartite graphs and graph products, Australas. J. Combin., 56, 47-60 (2013) · Zbl 1276.05099 |
| [3] | Adams, S. S.; Troxell, D. S.; Zinnen, S. L., Dynamic monopolies and feedback vertex sets in hexagonal grids, Comput. Math. Appl., 62, 4049-4057 (2011) · Zbl 1236.91099 · doi:10.1016/j.camwa.2011.09.047 |
| [4] | Bao, S.; Beineke, L. W., The decycling number of graphs, Australas. J. Combin., 25, 285-298 (2002) · Zbl 0994.05079 |
| [5] | Ben-Zwi, O.; Hermelin, D.; Lokshtanov, D., An exact almost optimal algorithm for target set selection in social networks, Proceedings of the tenth ACM conference on Electronic commerce (2009) |
| [6] | Beineke, L.; Vandell, R., Decycling graphs, J. Graph Theory, 25, 59-77 (1997) · Zbl 0870.05033 · doi:10.1002/(SICI)1097-0118(199705)25:1<59::AID-JGT4>3.0.CO;2-H |
| [7] | Berger, E., Dynamic monopolies of constant size, J. Combin. Theory Ser. B, 83, 191-200 (2001) · Zbl 1032.05052 · doi:10.1006/jctb.2001.2045 |
| [8] | Chen, N., On the approximability of influence in social networks, SIAM J. Discrete Math., 23, 1400-1415 (2009) · Zbl 1203.68314 · doi:10.1137/08073617X |
| [9] | Chiang, C. Y.; Huang, L. H.; Yeh, H. G., Target set selection problem for honeycomb networks, SIAM J. Discrete Math., 27, 310-328 (2013) · Zbl 1272.68063 · doi:10.1137/120868864 |
| [10] | Chiang, C. Y.; Huang, L. H.; Li, B. J.; Wu, J.; Yeh, H. G., Some results on the target set selection problem, J. Comb. Optim., 25, 702-715 (2011) · Zbl 1273.90224 · doi:10.1007/s10878-012-9518-3 |
| [11] | Chopin, M.; Nichterlein, A.; Niedermeier, R.; Weller, M., Constant thresholds can make target set selection tractable, Theory. Comput. Systems, 55, 61-83 (2014) · Zbl 1319.68109 · doi:10.1007/s00224-013-9499-3 |
| [12] | Compeau, P., Girth of pancake graphs, Discrete Appl. Math., 159, 1641-1645 (2011) · Zbl 1228.05166 · doi:10.1016/j.dam.2011.06.013 |
| [13] | Domingos, P.; Richardson, M., Mining the network value of customers, Seventh International Conference on Knowledge Discovery and Data Mining (2001) |
| [14] | Dreyer, P. A.; Roberts, F. S., Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion, Discrete Appl. Math., 157, 1615-1627 (2009) · Zbl 1163.92035 · doi:10.1016/j.dam.2008.09.012 |
| [15] | Iwasaki, T., Fault-tolerant routing in burnt pancake graphs, Inform. Process. Lett., 110, 535-538 (2010) · Zbl 1234.68325 · doi:10.1016/j.ipl.2010.04.023 |
| [16] | Festa, P.; Pardalos, P.; Resende, M. G C., Feedback set problems (1999), US: Springer, US · Zbl 1253.90193 |
| [17] | Flocchini, P.; Královič, R.; Ruzicka, P.; Santoro, N., On time versus size for monotone dynamic monopolies in regular topologies, J. Discrete Algorithms, 2, 135-156 (2002) |
| [18] | Flocchini, P.; Lodi, E.; Luccio, F.; Pagli, L.; Santoro, N., Dynamic monopolies in tori, Discrete Appl. Math., 137, 197-212 (2004) · Zbl 1104.90050 · doi:10.1016/S0166-218X(03)00261-0 |
| [19] | Heydari, M.; Sudborough, I., On sorting by prefix reversals and the dimaeter of pancake networks, Parallel Archirectures and Their Efficient Use, Lecture Notes in Computer Science, 678, 218-227 (1993) · doi:10.1007/3-540-56731-3_21 |
| [20] | Hoffman, C., Group theoretic algorithms and graph isomorphism (1982), New York: Springer, New York · Zbl 0487.68055 |
| [21] | Jung, S.; Kaneko, K., A feedback vertex set on pancake graphs, International Conference on Parallel and distributed Processing Techniques and Applications (2010) |
| [22] | Justan, M.; Muga, F. II; Sudborough, I., On the generalization of the pancake network, Proceedings of the International Symposium on Parallel Archiectures, Algorithms and Networks (2002) |
| [23] | Kaneko, K.; Suzuki, Y., Node-to-set disjoint paths problem in pancake graphs, IEICE Trans. Inf. Syst., E86-D, 1628-1633 (2003) |
| [24] | Kempe, D.; Kleinberg, J.; Tardos, E., Maximizing the spread of influence through a social network, Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2003) |
| [25] | Luccio, F., Almost exact minimum feedback vertex set in meshes and butterflies, Inform. Process. Lett., 66, 59-64 (1998) · Zbl 0925.68196 · doi:10.1016/S0020-0190(98)00039-8 |
| [26] | Peleg, D., Local majorities, coalitions and monopolies in graphs: A review, Theoret. Comput. Sci., 282, 231-257 (2002) · Zbl 0997.68088 · doi:10.1016/S0304-3975(01)00055-X |
| [27] | Pike, D. A.; Zou, Y., Decycling Cartesian products of two cycles, SIAM J. Discrete Math., 19, 651-663 (2005) · Zbl 1096.05030 · doi:10.1137/S089548010444016X |
| [28] | Zaker, M., On dynamic monopolies of graphs with general thresholds, Discrete Math., 312, 1136-1143 (2012) · Zbl 1238.05262 · doi:10.1016/j.disc.2011.11.038 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
