Data: 25/06/2020, às 14:00 horas (GMT-3, horário de Brasília).
Título: Dijkstra Graphs
Palestrante: Jayme Luiz Szwarcfiter (UFRJ e UERJ)


We re-visit a concept that has been, in a way, central in some early stages of computer science, that of structured programming. Basically it consists of a set of rules that an algorithm has to follow, in order to acquire a structure that is desired in many aspects. In spite of the fact that much has been written about structured programming, an important issue has been left unanswered: given an arbitrary algorithm, described by its flowchart, decide whether or not it is structured, that is, whether or not it follows the stated principles for structuring. By employing graph theoretic tools and algorithmic techniques, we formulate an efficient algorithm for answering this question. In order to do so, first we introduce the class of graphs which corresponds to the structured algorithms, which were then been named as Dijkstra Graphs. Our recognition problem then became to recognize graphs of this class. Further, we describe an efficient isomorphism algorithm for Dijkstra graphs. Both the recognition and isomorphism algorithms have complexity O(n), for graphs with n vertices.

Jointly with L. Bento, D. Boccardo, R. Machado, F. Miyazawa and V. Sá

Appeared in Discrete Applied Mathematics (2019)