{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T07:05:16Z","timestamp":1772694316497,"version":"3.50.1"},"reference-count":17,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2026,2]]},"abstract":"<jats:p>An r-role assignment of a simple graph G is an assignment of r distinct roles to the vertices of G, such that two vertices with the same role have the same set of roles assigned to related vertices. Furthermore, a specific r-role assignment defines a role graph, in which the vertices are the distinct r roles, and there is an edge between two roles whenever there are two adjacent vertices in the graph G that correspond to these roles. We consider complementary prisms, which are graphs formed from the disjoint union of the graph with its respective complement, adding the edges of a perfect matching between their corresponding vertices. In this work, we characterize the complementary prisms that do not admit a 3-role assignment and highlight that all of them are complementary prisms of disconnected bipartite graphs. Moreover, using our findings, we show that the problem of deciding whether a complementary prism has a 3-role assignment can be solved in polynomial time.<\/jats:p>","DOI":"10.1142\/s012905412550011x","type":"journal-article","created":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T02:57:36Z","timestamp":1745377056000},"page":"325-348","source":"Crossref","is-referenced-by-count":1,"title":["Computing a 3-Role Assignment is Polynomial-Time Solvable on Complementary Prisms"],"prefix":"10.1142","volume":"37","author":[{"given":"Diane","family":"Castonguay","sequence":"first","affiliation":[{"name":"Instituto de Inform\u00e1tica, Universidade Federal de Goi\u00e1s, Goi\u00e2nia, Goi\u00e1s, Brasil"}]},{"given":"Elis\u00e2ngela S.","family":"Dias","sequence":"additional","affiliation":[{"name":"Instituto de Inform\u00e1tica, Universidade Federal de Goi\u00e1s, Goi\u00e2nia, Goi\u00e1s, Brasil"}]},{"given":"Fernanda N.","family":"Mesquita","sequence":"additional","affiliation":[{"name":"Instituto de Inform\u00e1tica, Universidade Federal de Goi\u00e1s, Goi\u00e2nia, Goi\u00e1s, Brasil"}]},{"given":"Julliano R.","family":"Nascimento","sequence":"additional","affiliation":[{"name":"Instituto de Inform\u00e1tica, Universidade Federal de Goi\u00e1s, Goi\u00e2nia, Goi\u00e1s, Brasil"}]}],"member":"219","published-online":{"date-parts":[[2025,4,22]]},"reference":[{"key":"S012905412550011XBIB001","first-page":"82","volume-title":"Proc. 12th ACM Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing","author":"Angluin D.","year":"1980"},{"key":"S012905412550011XBIB002","first-page":"83","volume":"46","author":"Castonguay D.","year":"2018","journal-title":"Matem\u00e1tica Contempor\u00e2nea"},{"key":"S012905412550011XBIB003","doi-asserted-by":"crossref","first-page":"11","DOI":"10.21711\/231766362023\/rmc552","volume":"55","author":"Castonguay D.","year":"2023","journal-title":"Matem\u00e1tica Contempor\u00e2nea"},{"key":"S012905412550011XBIB004","doi-asserted-by":"publisher","DOI":"10.1051\/ro\/2023047"},{"key":"S012905412550011XBIB005","doi-asserted-by":"publisher","DOI":"10.1051\/ro\/2021192"},{"key":"S012905412550011XBIB006","unstructured":"T. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to algorithms,\n                      Massachusetts, EUA\n                      56\n                      (1) (MIT press, 2009) 115\u2013121."},{"issue":"1","key":"S012905412550011XBIB007","first-page":"85","volume":"74","author":"Chalopin J.","year":"2006","journal-title":"Fundamenta Informaticae"},{"key":"S012905412550011XBIB008","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.05.011"},{"key":"S012905412550011XBIB009","doi-asserted-by":"publisher","DOI":"10.1016\/0165-4896(91)90080-B"},{"key":"S012905412550011XBIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.029"},{"key":"S012905412550011XBIB011","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321926"},{"issue":"21","key":"S012905412550011XBIB012","first-page":"13","volume":"51","author":"Kleinberg J.","year":"2006","journal-title":"Pearson Education India"},{"issue":"21","key":"S012905412550011XBIB013","first-page":"13","volume":"51","author":"Haynes T. W.","year":"2007","journal-title":"Bulletin of the Institute of Combinatorics and Its Applications"},{"key":"S012905412550011XBIB014","first-page":"1","volume-title":"Tese (Doutorado em Ci\u00eancia da Computa\u00e7\u00e3o)","author":"Mesquita F. N.","year":"2022"},{"key":"S012905412550011XBIB015","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2015.08.001"},{"key":"S012905412550011XBIB016","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0037(200103)37:2<67::AID-NET1>3.0.CO;2-9"},{"key":"S012905412550011XBIB017","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.05.041"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905412550011X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T06:11:53Z","timestamp":1772691113000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S012905412550011X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,22]]},"references-count":17,"journal-issue":{"issue":"02","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["10.1142\/S012905412550011X"],"URL":"https:\/\/doi.org\/10.1142\/s012905412550011x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,22]]}}}