Dijkstra's Hypergraphs: Recognition and Isomorphism

• 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

Abstract

This paper introduces Dijkstra hypergraphs – directed hypergraphs modelling the execution of structured parallel programs through flow hypergraphs. Dijkstra hypergraphs arised from the concept of Dijkstra structured programming, the concept of multiprogramming of Hansen and Dijkstra et al. and the Dijkstra graphs of Bento et al. Linear time algorithms are provided to recognize and to check isomorphism of Dijkstra hypergraphs.

References

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.