LINEAR-TIME ALGORITHM FOR TESTING THE TRUTH OF CERTAIN QUANTIFIED BOOLEAN FORMULAS

被引：538

作者：

ASPVALL, B

PLASS, MF

TARJAN, RE

机构：

[1] Computer Science Department, Stanford University, Stanford

来源：

基金：

美国国家科学基金会;

关键词：

2-CNF; 2-satisfiability; Quantified Boolean formula; strongly connected components;

D O I：

10.1016/0020-0190(79)90002-4

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

[No abstract available]

引用

页码：121 / 123

页数：3

共 7 条

[1]

Aho, Hopcroft, Ullman, The Design and Analysis of Computer Algorithms, (1974)

[2]

Cook, The complexity of theorem proving procedures, Proc. 3rd Ann. ACM Symp. Theory Comput., pp. 151-158, (1971)

[3]

Even, Itai, Shamir, On the complexity of timetable and multi-commodity flow problems, SIAM Journal on Computing, 5, 4, pp. 691-703, (1976)

[4]

Reingold, Nievergelt, Deo, Combinatorial Algorithms: Theory and Practice, (1977)

[5]

Schaefer, The complexity of satisfiability problems, Proc. 10th Ann. ACM Symp. Theory Comput., pp. 216-226, (1978)

[6]

Stockmeyer, Meyer, Word problems requiring exponential time, Proc. 5th Ann. ACM Symp. Theory Comput., pp. 1-9, (1973)

[7]

Tarjan, Depth first search and linear graph algorithms, SIAM Journal on Computing, 1, 2, pp. 146-160, (1972)