PROBABILISTIC ANALYSIS OF 2 HEURISTICS FOR THE 3-SATISFIABILITY PROBLEM

被引：62

作者：

CHAO, MT ^{[1
]}

FRANCO, J ^{[1
]}

机构：

[1] INDIANA UNIV,DEPT COMP SCI,BLOOMINGTON,IN 47405

来源：

SIAM JOURNAL ON COMPUTING | 1986年 / 15卷 / 04期

关键词：

D O I：

10.1137/0215080

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：1106 / 1118

页数：13

共 11 条

[1] AN AVERAGE TIME ANALYSIS OF BACKTRACKING [J].

BROWN, CA ;

PURDOM, PW .

SIAM JOURNAL ON COMPUTING, 1981, 10 (03) :583-593

[2]

CHAO MT, 1984, THESIS CASE W RESERV

[3] A COMPUTING PROCEDURE FOR QUANTIFICATION THEORY [J].

DAVIS, M ;

PUTNAM, H .

JOURNAL OF THE ACM, 1960, 7 (03) :201-215

[4]

Erdos P., 1974, PROBABILISTIC METHOD

[5] PROBABILISTIC ANALYSIS OF THE DAVIS PUTNAM PROCEDURE FOR SOLVING THE SATISFIABILITY PROBLEM [J].

FRANCO, J ;

PAULL, M .

DISCRETE APPLIED MATHEMATICS, 1983, 5 (01) :77-87

[6]

Franco J., 1984, Annals of Operations Research, V1, P273, DOI 10.1007/BF01874393

[7]

FRANCO J, UNPUB INFORM PROCESS

[8] AVERAGE TIME ANALYSES OF SIMPLIFIED DAVIS-PUTNAM PROCEDURES [J].

GOLDBERG, A ;

PURDOM, P ;

BROWN, C .

INFORMATION PROCESSING LETTERS, 1982, 15 (02) :72-75

[9] SEARCH REARRANGEMENT BACKTRACKING AND POLYNOMIAL AVERAGE TIME [J].

PURDOM, PW .

ARTIFICIAL INTELLIGENCE, 1983, 21 (1-2) :117-133

[10]

PURDOM PW, 1985, SIAM J COMPUT, V14, P943, DOI 10.1137/0214067

← 1 2 →