Dijkstra graphs

被引：9

作者：

Bento, Lucila M. S. ^{[2
]}

Boccardo, Davidson R. ^{[2
]}

Machado, Raphael C. S. ^{[3
,4
]}

Miyazawa, Flavio K. ^{[6
]}

Pereira de Sa, Vinicius G. ^{[1
]}

Szwarcfiter, Jayme L. ^{[1
,5
]}

机构：

[1] UFRJ Fed Univ Rio de Janeiro, Rio De Janeiro, Brazil

[2] Clavis Informat Secur Grp, Rio De Janeiro, Brazil

[3] INMETRO Natl Inst Metrol Qual & Technol, Duque De Caxias, Brazil

[4] CEFET RJ Fed Ctr Technol Educ, Rio De Janeiro, Brazil

[5] UERJ State Univ Rio de Janeiro, Rio De Janeiro, Brazil

[6] UNICAMP Univ Campinas, Campinas, SP, Brazil

来源：

DISCRETE APPLIED MATHEMATICS | 2019年 / 261卷

基金：

巴西圣保罗研究基金会;

关键词：

Graph algorithms; Graph isomorphism; Reducibility; Structured programming; FLOW DIAGRAMS;

D O I：

10.1016/j.dam.2017.07.033

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. (C) 2017 Elsevier B.V. All rights reserved.

引用

页码：52 / 62

页数：11

共 27 条

[1]

[Anonymous], 1976, ICSE 76

[2]

[Anonymous], 1972, Chapter I: Notes on structured programming, em Structured programming

[3]

Bento L. M. S., 2013, PROVABLY RESILIENT S, P50

[4] FLOW DIAGRAMS TURING MACHINES AND LANGUAGES WITH ONLY 2 FORMATION RULES [J].

BOHM, C ;

JACOPINI, G .

COMMUNICATIONS OF THE ACM, 1966, 9 (05) :366-&

[5]

Collberg C, 2003, LECT NOTES COMPUT SC, V2880, P156

[6]

Dahl O.-J., 1972, Structured programming, P175

[7] GO TO STATEMENT CONSIDERED HARMFUL [J].

DIJKSTRA, EW .

COMMUNICATIONS OF THE ACM, 1968, 11 (03) :147-&

[8] A GENERALIZED MATHEMATICAL-THEORY OF STRUCTURED PROGRAMMING [J].

FENTON, NE ;

WHITTY, RW ;

KAPOSI, AA .

THEORETICAL COMPUTER SCIENCE, 1985, 36 (2-3) :145-171

[9] ON FOLK THEOREMS [J].

HAREL, D .

COMMUNICATIONS OF THE ACM, 1980, 23 (07) :379-389

[10]

Hecht MatthewS., 1972, Proceedings of the fourth annual ACM symposium on Theory of computing, STOC '72, P238

← 1 2 3 →