On the complexity of dualization of monotone disjunctive normal forms

被引：275
作者：
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 ;
摘要：
We show that the duality of a pair of monotone disjunctive normal forms of size n can be tested in n(O(log n)) time. (C) 1996 Academic Press, Inc.
引用
收藏
页码：618 / 628
页数：11
相关论文
共 15 条
  • [1] 3-CHROMATIC HYPERGRAPHS
    BECK, J
    [J]. DISCRETE MATHEMATICS, 1978, 24 (02) : 127 - 137
  • [2] COMPLEXITY OF IDENTIFICATION AND DUALIZATION OF POSITIVE BOOLEAN FUNCTIONS
    BIOCH, JC
    IBARAKI, T
    [J]. 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
    GARCIAMOLINA, H
    BARBARA, D
    [J]. 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
    JOHNSON, DS
    YANNAKAKIS, M
    PAPADIMITRIOU, CH
    [J]. INFORMATION PROCESSING LETTERS, 1988, 27 (03) : 119 - 123
12