Computing role assignments of Cartesian product of graphs

DOI10.1051/RO/2023047MaRDI QIDQ6050574zbMATH OpenOpenAlexFDO

Authors Diane Castonguay, Elisângela Silva Dias, Fernanda Neiva Mesquita, Julliano Rosa Nascimento

Publication date 19 September 2023

Published in RAIRO - Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1051/ro/2023047

zbMATH Keywords

Cartesian productcomputational complexityrole assignment

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Computing some role assignments of Cartesian product of graphs
• A complete complexity classification of the role assignment problem
• Computing Role Assignments of Chordal Graphs
• Computing role assignments of chordal graphs
• How hard is it to determine if a graph has a 2-role assignment?

Cited in

(5)

• Computing Role Assignments of Chordal Graphs
• scientific article; zbMATH DE number 1302393 (Why is no real title available?)
• Computing some role assignments of Cartesian product of graphs
• Study on (r+1)-role assignments of complementary prisms, with r 3
• Computing a 3-role assignment is polynomial-time solvable on complementary prisms

This page was built for publication: Computing role assignments of Cartesian product of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6050574)