DECIDING FRATTINI IS NP-COMPLETE

被引：4

作者：

RYTER, CH ^{[1
]}

SCHMID, J ^{[1
]}

机构：

[1] UNIV BERN,DEPT MATH,CH-3012 BERN,SWITZERLAND

来源：

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS | 1994年 / 11卷 / 03期

关键词：

PARTIALLY ORDERED SET; FRATTINI SUBLATTICE; NP-COMPLETE;

D O I：

10.1007/BF02115815

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that it is a NP-complete problem to decide whether a finite poset arises as the (Birkhoff) dual of the Frattini sublattice of some finite distributive lattice.

引用

页码：257 / 279

页数：23

共 13 条

[1]

ABAD M, 1994, IN PRESS ALGEBRA UNI

[2]

ADAMS ME, 1973, ALGEBR UNIV, V3, P216

[3]

ADAMS ME, 1981, COLLOQ MATH, V44, P181

[4]

CHEN CC, 1973, ALGEBR UNIV, V3, P294

[5]

CHEN CC, 1975, ALGEBRA UNIV, V5, P88

[6] REMARKS ON PRIESTLEY DUALITY FOR DISTRIBUTIVE LATTICES [J].

CIGNOLI, R ;

LAFALCE, S ;

PETROVICH, A .

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1991, 8 (03) :299-315

[7]

Davey B.A., 1992, INTRO LATTICES ORDER

[8]

Garey M. R., 1979, COMPUTERS INTRACTABI

[9]

Hashimoto J., 1952, MATH JAPANICAE, V2, P149

[10]

KOH KM, 1971, ALGEBRA UNIV, V1, P104

← 1 2 →