Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/337760
Type: Artigo
Title: Dijkstra graphs
Author: Bento, Lucila M. S.
Boccardo, Davidson R.
Machado, Raphael C. S.
Miyazawa, Flavio K.
Pereira de Sa, Vinicius G.
Szwarcfiter, Jayme L.
Abstract: We revisit a concept that has been central in some early stages of computer science, that of structured programming: a set of rules that an algorithm must follow in order to acquire a certain desirable structure. While much has been written about structured programming, an important issue has been left unanswered: given an arbitrary program, describe an algorithm to decide whether or not it is structured, that is, whether it conforms to the stated principles of structured programming. We refer to a classical concept of structured programming, as described by Dijkstra. By employing graph theoretic techniques, we formulate an efficient algorithm for answering this question. First, we introduce the class of graphs which correspond to structured programs, which we call Dijkstra Graphs. Then we present a greedy O(n)-time algorithm for recognizing such graphs. Furthermore, we describe an isomorphism algorithm for Dijkstra graphs, whose complexity is also linear in the number of vertices of the graph
Subject: Algoritmos em grafos
Country: Países Baixos
Editor: Elsevier
Rights: Fechado
Identifier DOI: 10.1016/j.dam.2017.07.033
Address: https://www.sciencedirect.com/science/article/pii/S0166218X17303554
Date Issue: 2019
Appears in Collections:IC - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
000468260200006.pdf512.64 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.