TESTING FLOW GRAPH REDUCIBILITY.

Research output: Contribution to conferencePaperpeer-review

35 Scopus citations

Abstract

This paper presents an algorithm with an almost-linear time bound for determining whether a flow graph is reducible. The algorithm may be used to determine a way to reduce the graph if such a way exists. The method uses depth-first search and a good algorithm for computing disjoint set unions, and it improves upon a previously published algorithm for determining reducibility. The algorithm may be used as a basic subroutine for various code optimization procedures.

Original languageEnglish (US)
Pages96-107
Number of pages12
StatePublished - Jan 1 1973
EventACM Symp on Theory of Comput, 5th Annu, Proc, Conf Rec, Pap - Austin, Tex
Duration: Apr 30 1973May 2 1973

Other

OtherACM Symp on Theory of Comput, 5th Annu, Proc, Conf Rec, Pap
CityAustin, Tex
Period4/30/735/2/73

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'TESTING FLOW GRAPH REDUCIBILITY.'. Together they form a unique fingerprint.

Cite this