TESTING FLOW GRAPH REDUCIBILITY.

Robert Tarjan

TESTING FLOW GRAPH REDUCIBILITY.

Research output: Contribution to conference › Paper › peer-review

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 language	English (US)
Pages	96-107
Number of pages	12
State	Published - 1973
Event	ACM Symp on Theory of Comput, 5th Annu, Proc, Conf Rec, Pap - Austin, Tex Duration: Apr 30 1973 → May 2 1973

Other

Other	ACM Symp on Theory of Comput, 5th Annu, Proc, Conf Rec, Pap
City	Austin, Tex
Period	4/30/73 → 5/2/73

All Science Journal Classification (ASJC) codes

General Engineering

Cite this

@conference{7be7de5de10e4c17a9ec2cc2d86dba40,

title = "TESTING FLOW GRAPH REDUCIBILITY.",

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.",

author = "Robert Tarjan",

note = "Funding Information: * This research was partially supported by the National Science Foundation, Contract No. NSF-GJ-35604X, and by a Miller Research Fellowship.; ACM Symp on Theory of Comput, 5th Annu, Proc, Conf Rec, Pap ; Conference date: 30-04-1973 Through 02-05-1973",

year = "1973",

language = "English (US)",

pages = "96--107",

}

TY - CONF

T1 - TESTING FLOW GRAPH REDUCIBILITY.

AU - Tarjan, Robert

N1 - Funding Information: * This research was partially supported by the National Science Foundation, Contract No. NSF-GJ-35604X, and by a Miller Research Fellowship.

PY - 1973

Y1 - 1973

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0015774177&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0015774177&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0015774177

SP - 96

EP - 107

T2 - ACM Symp on Theory of Comput, 5th Annu, Proc, Conf Rec, Pap

Y2 - 30 April 1973 through 2 May 1973

ER -

TESTING FLOW GRAPH REDUCIBILITY.

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this