On the complexity of dualization of monotone disjunctive normal forms

被引：277

作者：

Fredman, ML

Khachiyan, L

机构：

[1] Department of Computer Science, Rutgers University, New Brunswick

来源：

JOURNAL OF ALGORITHMS | 1996年 / 21卷 / 03期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1006/jagm.1996.0062

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：618 / 628

页数：11

共 15 条

[1] 3-CHROMATIC HYPERGRAPHS [J].

BECK, J .

DISCRETE MATHEMATICS, 1978, 24 (02) :127-137

[2] COMPLEXITY OF IDENTIFICATION AND DUALIZATION OF POSITIVE BOOLEAN FUNCTIONS [J].

BIOCH, JC ;

IBARAKI, T .

INFORMATION AND COMPUTATION, 1995, 123 (01) :50-63

[3]

BSHOUTY NH, P 7 ANN ACM C COMP L, P130

[4]

EITER T, 1995, SIAM J COMPUT, V24

[5]

ERDOS P, 1963, NORD MAT TIDSKRIFT, V11, P1

[6] HOW TO ASSIGN VOTES IN A DISTRIBUTED SYSTEM [J].

GARCIAMOLINA, H ;

BARBARA, D .

JOURNAL OF THE ACM, 1985, 32 (04) :841-860

[7]

GURVICH V, 1995, IN PRESS DISCRETE AP

[8]

GURVICH V, 1975, USSR COMP MATH MATH, V15, P357

[9]

IBARAKI T, 1991, 3RD P IEEE S PAR DIS, P150

[10] ON GENERATING ALL MAXIMAL INDEPENDENT SETS [J].

JOHNSON, DS ;

YANNAKAKIS, M ;

PAPADIMITRIOU, CH .

INFORMATION PROCESSING LETTERS, 1988, 27 (03) :119-123

← 1 2 →