Hipergrafos de Dijkstra: Reconhecimento e Isomorfismo

• Leonardo de Almeida Cavadas UERJ
• Luerbio Faria UERJ
• Lucila Maria de Souza Bento UERJ
• Jayme Luiz Szwarcfiter UERJ / UFRJ
• André Luiz Pires Guedes UFPR
• Lilian Markenzon UFRJ

DOI: https://doi.org/10.5753/etc.2024.2998

Resumo

Este artigo introduz os hipergrafos de Dijkstra – hipergrafos direcionados que modelam a execução de programas paralelos estruturados, através de hipergrafos de fluxo. Hipergrafos de Dijkstra foram criados a partir do conceito de programação estruturada de Dijkstra, da multiprogramação de Hansen e de Dijkstra et al. e dos grafos de Dijkstra de Bento et al. Algoritmos de tempo linear são fornecidos para reconhecer e verificar o isomorfismo dos hipergrafos de Dijkstra.

Referências

Bento, L. M. d. S., Boccardo, D. R., Machado, R. C. S., Miyazawa, F. K., de Sá, V. G. P., and Szwarcfiter, J. L. (2019). Dijkstra graphs. Discrete Applied Mathematics, 261:52–62.

Dijkstra, E. W. (1968). The structure of“the”-multiprogramming system. Communications of the ACM, 11(5):341–346.

Dijkstra, E. W., Dahl, O.-J., and Hoare, C. A. R. (1972). Structured programming. Academic Press Ltd.

Guedes, A. L. P., Markenzon, L., and Faria, L. (2011). Flow hypergraph reducibility. Discrete applied mathematics, 159(16):1775–1785.

Hansen, P. B. (1972). Structured multiprogramming. Communications of the ACM, 15(7):574–578.

Hecht, M. S. and Ullman, J. D. (1972). Flow graph reducibility. In Proceedings of the fourth annual ACM symposium on Theory of computing, pages 238–250.

Hecht, M. S. and Ullman, J. D. (1974). Characterizations of reducible flow graphs. Journal of the ACM (JACM), 21(3):367–375.