Abstrakt. Låt A vara en m×n binär matris, t... {1,.., m} vara en tröskel, och ε > 0 vara en positiv parameter. Vi visar att med tanke på en familj av O (n ε ) maximal t- frekventa kolumnuppsättningar för A, är det NP-komplett att avgöra om A har några ytterligare maximal t- frekventa uppsättningar, eller inte, även när antalet sådana ytterligare maximal t- frekventa kolumnuppsättningar kan vara exponentiellt stora. I motsats kan alla minimala t-in frekventa uppsättningar kolumner av A räknas i inkrementell kvasi-polynom tid. Beviset för det senare resultatet följer av ojämlikheten α ≤ (m − t + 1) β, där α respektive β är talen för alla maximal t- frekventa och alla minimala t-in frekventa uppsättningar kolumner i matris A. Vi diskuterar också komplexiteten i att generera alla slutna t-ofta kolumnuppsättningar för en given binär matris.
Boros m.fl. REF visade att det, med tanke på en familj av O(n ε ) maximal frekventa mönster, är NP-komplett att avgöra om X har ytterligare maximal frekventa mönster (för godtyckligt små fasta ε > 0), och att alla minimala ovanliga mönster kan räknas i inkrementell kvasipolynom tid.
On the Complexity of Generating Maximal Frequent and Minimal Infrequent Sets
{'venue': 'STACS', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}