In social networks, a role assignment is such that individuals play the same role, if they relate in the same way to other individuals playing counterpart roles. When a smaller graph models the social roles in a network, this gives rise to the decision problem called r-Role Assignment whether it exists such an assignment of r distinct roles to the vertices of the graph. This problem is known to be NP-complete for any fixed r ≥ 2. The Cartesian product of graphs is one of the most studied operation on graphs and has numerous applications in diverse areas, such as Mathematics, Computer Science, Chemistry and Biology. In this paper, we determine the computational complexity of r-Role Assignment restricted to Cartesian product of graphs, for r = 2, 3. In fact, we show that the Cartesian product of graphs is always 2-role assignable, however the problem of 3-Role Assignment is still NP-complete for this class.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2021192
Keywords: Role assignment, Cartesian product, computational complexity
@article{RO_2022__56_1_115_0,
author = {Castonguay, Diane and Silva Dias, Elisangela and Mesquita, Fernanda Neiva and Nascimento, Julliano Rosa},
title = {Computing some role assignments of {Cartesian} product of graphs},
journal = {RAIRO. Operations Research},
pages = {115--121},
year = {2022},
publisher = {EDP-Sciences},
volume = {56},
number = {1},
doi = {10.1051/ro/2021192},
mrnumber = {4376293},
zbl = {1483.91156},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021192/}
}
TY - JOUR AU - Castonguay, Diane AU - Silva Dias, Elisangela AU - Mesquita, Fernanda Neiva AU - Nascimento, Julliano Rosa TI - Computing some role assignments of Cartesian product of graphs JO - RAIRO. Operations Research PY - 2022 SP - 115 EP - 121 VL - 56 IS - 1 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021192/ DO - 10.1051/ro/2021192 LA - en ID - RO_2022__56_1_115_0 ER -
%0 Journal Article %A Castonguay, Diane %A Silva Dias, Elisangela %A Mesquita, Fernanda Neiva %A Nascimento, Julliano Rosa %T Computing some role assignments of Cartesian product of graphs %J RAIRO. Operations Research %D 2022 %P 115-121 %V 56 %N 1 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021192/ %R 10.1051/ro/2021192 %G en %F RO_2022__56_1_115_0
Castonguay, Diane; Silva Dias, Elisangela; Mesquita, Fernanda Neiva; Nascimento, Julliano Rosa. Computing some role assignments of Cartesian product of graphs. RAIRO. Operations Research, Tome 56 (2022) no. 1, pp. 115-121. doi: 10.1051/ro/2021192
[1] , Local and global properties in networks of processors, In: Proc. 12th ACM Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing (1980) 82–93. | DOI
[2] , and , Prismas complementares com 2-atribuiçao de papéis. Mat. Contemp. 46 (2018) 83–93. | MR | Zbl
[3] , and , Election, naming and cellular edge local computations. In: International Conference on Graph Transformation (ICGT 2004) (EATCS Best Paper Award). Springer, Italy (2004) 242–256. | MR | Zbl
[4] , and , Local computations in graphs: the case of cellular edge local computations. Fund. Inf. 74 (2006) 85–114. | MR | Zbl
[5] , and , Matching preclusion number in cartesian product of graphs and its application to interconnection networks. ARS Comb. 112 (2013) 193–204. | MR | Zbl
[6] , Computing role assignments of split graphs. Theor. Comput. Sci. 635 (2016) 74–84. | MR | Zbl | DOI
[7] , , , , , and , Fall colorings of graphs. J. Comb. Math. Comb. Comput. 33 (2000) 257–274. | MR | Zbl
[8] and , Role colouring a graph. Math. Soc. Sci. 21 (1991) 183–188. | MR | Zbl | DOI
[9] and , A complete complexity classification of the role assignment problem. Theor. Comput. Sci. 349 (2005) 67–81. | MR | Zbl | DOI
[10] and , Comparing universal covers in polynomial time. Theor. Comput. Syst. 46 (2010) 620–635. | MR | Zbl | DOI
[11] and , Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., New York, USA (1979). | Zbl
[12] , and , Handbook of Product Graphs. Vol. 2. CRC Press, Boca Raton (2011). | MR | Zbl | DOI
[13] , and , Computing role assignments of proper interval graphs in polynomial time. J. Discrete Algorithms 14 (2012) 173–188. | MR | Zbl | DOI
[14] and , Graph products for configuration processing of space structures. Comput. Struct. 86 (2008) 1219–1231. | DOI
[15] and , Fall colouring of bipartite graphs and cartesian products of graphs. Discrete Appl. Math. 157 (2009) 330–338. | MR | Zbl | DOI
[16] and , The role assignment model nearly fits most social networks. Math. Soc. Sci. 41 (2001) 275–293. | MR | Zbl | DOI
[17] and , How hard is it to determine if a graph has a 2-role assignment? Networks Int. J. 37 (2001) 67–73. | MR | Zbl
[18] , Graph multiplication. Math. Z. 72 (1959) 446–457. | MR | Zbl | DOI
[19] , and , Computing role assignments of chordal graphs. Theor. Comput. Sci. 411 (2010) 3601–3613. | MR | Zbl | DOI
[20] , Design and analysis of product networks. In: Proceedings Frontiers’ 95. The Fifth Symposium on the Frontiers of Massively Parallel Computation. IEEE (1995) 521–528.
[21] , , and , k-role assignments under some graph operations. J. Hebei Univ. Sci. Technol. (2010).
Cité par Sources :
