research-article

A Complexity Measure

Author:

T. J. McCabeAuthors Info & Claims

IEEE Transactions on Software Engineering, Volume 2, Issue 4

Pages 308 - 320

https://doi.org/10.1109/TSE.1976.233837

Published: 01 July 1976 Publication History

Publisher Site

Abstract

This paper describes a graph-theoretic complexity measure and illustrates how it can be used to manage and control program complexity. The paper first explains how the graph-theory concepts apply and gives an intuitive explanation of the graph concepts in programming terms. The control graphs of several actual Fortran programs are then presented to illustrate the correlation between intuitive complexity and the graph-theoretic complexity. Several properties of the graph-theoretic complexity are then proved which show, for example, that complexity is independent of physical size (adding or subtracting functional statements leaves complexity unchanged) and complexity depends only on the decision structure of a program.

Cited By

View all

Tiwana ASafadi H(2024)Atrophy in Aging SystemsInformation Systems Research10.1287/isre.2023.121835:1(66-86)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1287/isre.2023.1218
Wang ZLiu KLi GJin ZFilkov VRay BZhou M(2024)HITS: High-coverage LLM-based Unit Test Generation via Method SlicingProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695501(1258-1268)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695501
Yang WGao CLiu XLi YXue YFilkov VRay BZhou M(2024)Rust-twins: Automatic Rust Compiler Testing through Program Mutation and Dual Macros GenerationProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695059(631-642)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695059
Show More Cited By

A Complexity Measure
1. Mathematics of computing
  1. Discrete mathematics

Recommendations

A complexity measure
ICSE '76: Proceedings of the 2nd international conference on Software engineering

This paper describes a graph-theoretic complexity measure and illustrates how it can be used to manage and control program complexity. The paper first explains how the graph theory concepts apply and gives an intuitive explanation of the graph concepts ...
A measure of logical complexity of programs

The research in software science has so far been concentrated on three measures of program complexity: (a) software effort; (b) cyclomatic complexity; and (c) program knots. In this paper we propose a measure of the logical complexity of programs in ...
Discrete Systems and Flowcharts

This paper points out the abstract similarities between problems arising in programming, discrete systems analysis in engineering, and network flow problems in operations research. The highly developed techniques of analyzing discrete systems of two ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Software Engineering

IEEE Transactions on Software Engineering Volume 2, Issue 4

July 1976

95 pages

ISSN:0098-5589

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 July 1976

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

89
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Tiwana ASafadi H(2024)Atrophy in Aging SystemsInformation Systems Research10.1287/isre.2023.121835:1(66-86)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1287/isre.2023.1218
Wang ZLiu KLi GJin ZFilkov VRay BZhou M(2024)HITS: High-coverage LLM-based Unit Test Generation via Method SlicingProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695501(1258-1268)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695501
Yang WGao CLiu XLi YXue YFilkov VRay BZhou M(2024)Rust-twins: Automatic Rust Compiler Testing through Program Mutation and Dual Macros GenerationProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695059(631-642)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695059
She XZhao YWang HFilkov VRay BZhou M(2024)WaDec: Decompiling WebAssembly Using Large Language ModelProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695020(481-492)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695020
Hickman HBell T(2024)Using Conditions and Control Structures Effectively: Can We Measure This?Proceedings of the 19th WiPSCE Conference on Primary and Secondary Computing Education Research10.1145/3677619.3678128(1-2)Online publication date: 16-Sep-2024
https://dl.acm.org/doi/10.1145/3677619.3678128
Hickman HBell T(2024)Automated Assessment: Does It Align With Teachers' Views?Proceedings of the 19th WiPSCE Conference on Primary and Secondary Computing Education Research10.1145/3677619.3678113(1-10)Online publication date: 16-Sep-2024
https://dl.acm.org/doi/10.1145/3677619.3678113
Pisch ECai YKazman RLefever JFang H(2024)M-score: An Empirically Derived Software Modularity MetricProceedings of the 18th ACM/IEEE International Symposium on Empirical Software Engineering and Measurement10.1145/3674805.3686697(382-392)Online publication date: 24-Oct-2024
https://dl.acm.org/doi/10.1145/3674805.3686697
Hou YJin WWang ZWang LChen SWang YSang LWang HLiu T(2024)ERD-CQC : Enhanced Rule and Dependency Code Quality Check for JavaProceedings of the 15th Asia-Pacific Symposium on Internetware10.1145/3671016.3674820(377-386)Online publication date: 24-Jul-2024
https://dl.acm.org/doi/10.1145/3671016.3674820
Rasch A(2024)(De/Re)-Composition of Data-Parallel Computations via Multi-Dimensional HomomorphismsACM Transactions on Programming Languages and Systems10.1145/366564346:3(1-74)Online publication date: 10-Oct-2024
https://dl.acm.org/doi/10.1145/3665643
Romano SToriello GCassieri PFrancese RScanniello G(2024)A Folklore Confirmation on the Removal of Dead CodeProceedings of the 28th International Conference on Evaluation and Assessment in Software Engineering10.1145/3661167.3661188(333-338)Online publication date: 18-Jun-2024
https://dl.acm.org/doi/10.1145/3661167.3661188
Show More Cited By

Abstract

Cited By

Recommendations