{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T13:41:55Z","timestamp":1771854115784,"version":"3.50.1"},"reference-count":21,"publisher":"EDP Sciences","issue":"1","license":[{"start":{"date-parts":[[2022,2,7]],"date-time":"2022-02-07T00:00:00Z","timestamp":1644192000000},"content-version":"vor","delay-in-days":37,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005285","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de Goi\u00e1s","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005285","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2021,12,23]]},"published-print":{"date-parts":[[2022,1]]},"abstract":"<jats:p>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 <jats:italic>r<\/jats:italic>-R<jats:sc>ole<\/jats:sc> A<jats:sc>ssignment<\/jats:sc> whether it exists such an assignment of <jats:italic>r<\/jats:italic> distinct roles to the vertices of the graph. This problem is known to be <jats:bold>NP<\/jats:bold>-complete for any fixed <jats:italic>r<\/jats:italic> \u2265 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 <jats:italic>r<\/jats:italic>-R<jats:sc>ole<\/jats:sc> A<jats:sc>ssignment<\/jats:sc> restricted to Cartesian product of graphs, for <jats:italic>r<\/jats:italic> = 2, 3. In fact, we show that the Cartesian product of graphs is always 2-role assignable, however the problem of 3-R<jats:sc>ole<\/jats:sc> A<jats:sc>ssignment<\/jats:sc> is still <jats:bold>NP<\/jats:bold>-complete for this class.<\/jats:p>","DOI":"10.1051\/ro\/2021192","type":"journal-article","created":{"date-parts":[[2021,12,30]],"date-time":"2021-12-30T19:50:33Z","timestamp":1640893833000},"page":"115-121","source":"Crossref","is-referenced-by-count":5,"title":["Computing some role assignments of Cartesian product of graphs"],"prefix":"10.1051","volume":"56","author":[{"given":"Diane","family":"Castonguay","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1132-1518","authenticated-orcid":false,"given":"Elisangela","family":"Silva Dias","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2010-4088","authenticated-orcid":false,"given":"Fernanda Neiva","family":"Mesquita","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3002-5172","authenticated-orcid":false,"given":"Julliano Rosa","family":"Nascimento","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2022,2,7]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Angluin D., 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\u201393.","DOI":"10.1145\/800141.804655"},{"key":"R2","first-page":"83","volume":"46","author":"Castonguay","year":"2018","journal-title":"Mat. Contemp."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Chalopin J., M\u00e9tivier Y. and Zielonka W., Election, naming and cellular edge local computations. In: International Conference on Graph Transformation (ICGT 2004) (EATCS Best Paper Award). Springer, Italy (2004) 242\u2013256.","DOI":"10.1007\/978-3-540-30203-2_18"},{"key":"R4","first-page":"85","volume":"74","author":"Chalopin","year":"2006","journal-title":"Fund. Inf."},{"key":"R5","first-page":"193","volume":"112","author":"de Almeida","year":"2013","journal-title":"ARS Comb."},{"key":"R6","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1016\/j.tcs.2016.05.011","volume":"635","author":"Dourado","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"R7","first-page":"257","volume":"33","author":"Dunbar","year":"2000","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"R8","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0165-4896(91)90080-B","volume":"21","author":"Everett","year":"1991","journal-title":"Math. Soc. Sci."},{"key":"R9","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.tcs.2005.09.029","volume":"349","author":"Fiala","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"R10","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1007\/s00224-009-9200-z","volume":"46","author":"Fiala","year":"2010","journal-title":"Theor. Comput. Syst."},{"key":"R11","unstructured":"Garey M.R. and Johnson D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., New York, USA (1979)."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Hammack R.H., Imrich W. and Klav\u017ear S., Handbook of Product Graphs. Vol. 2. CRC Press, Boca Raton (2011).","DOI":"10.1201\/b10959"},{"key":"R13","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/j.jda.2011.12.004","volume":"14","author":"Heggernes","year":"2012","journal-title":"J. Discrete Algorithms"},{"key":"R14","doi-asserted-by":"crossref","first-page":"1219","DOI":"10.1016\/j.compstruc.2007.11.005","volume":"86","author":"Kaveh","year":"2008","journal-title":"Comput. Struct."},{"key":"R15","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1016\/j.dam.2008.03.003","volume":"157","author":"Laskar","year":"2009","journal-title":"Discrete Appl. Math."},{"key":"R16","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/S0165-4896(00)00064-0","volume":"41","author":"Peke\u010d","year":"2001","journal-title":"Math. Soc. Sci."},{"key":"R17","first-page":"67","volume":"37","author":"Roberts","year":"2001","journal-title":"Networks Int. J."},{"key":"R18","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1007\/BF01162967","volume":"72","author":"Sabidussi","year":"1959","journal-title":"Math. Z."},{"key":"R19","doi-asserted-by":"crossref","first-page":"3601","DOI":"10.1016\/j.tcs.2010.05.041","volume":"411","author":"van \u2018t Hof","year":"2010","journal-title":"Theor. Comput. Sci."},{"key":"R20","unstructured":"Youssef A., Design and analysis of product networks. In: Proceedings Frontiers\u2019 95. The Fifth Symposium on the Frontiers of Massively Parallel Computation. IEEE (1995) 521\u2013528."},{"key":"R21","unstructured":"Zhao Y.-Q., Feng W.-L., Li H. and Yang J.-M., k-role assignments under some graph operations. J. Hebei Univ. Sci. Technol. (2010)."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2021192\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,7]],"date-time":"2022-02-07T09:14:59Z","timestamp":1644225299000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2021192"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1]]},"references-count":21,"journal-issue":{"issue":"1"},"alternative-id":["ro210361"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2021192","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"2804-7303","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1]]}}}