TY - GEN

T1 - An algorithm for dualization in products of lattices and its applications

AU - Elbassioni, Khaled M.

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.

PY - 2002

Y1 - 2002

N2 - Let L = L1x ••• x Lnbe the product of n lattices, each of which has a bounded width. Given a subset A⊆L, we show that the problem of extending a given partial list of maximal independent elements of A in L can be solved in quasi-polynomial time. This result implies, in particular, that the problem of generating all minimal infrequent elements for a database with semi-lattice attributes, and the problem of generating all maximal boxes that contain at most a specified number of points from a given n-dimensional point set, can both be solved in incremental quasi-polynomial time.

AB - Let L = L1x ••• x Lnbe the product of n lattices, each of which has a bounded width. Given a subset A⊆L, we show that the problem of extending a given partial list of maximal independent elements of A in L can be solved in quasi-polynomial time. This result implies, in particular, that the problem of generating all minimal infrequent elements for a database with semi-lattice attributes, and the problem of generating all maximal boxes that contain at most a specified number of points from a given n-dimensional point set, can both be solved in incremental quasi-polynomial time.

UR - http://www.scopus.com/inward/record.url?scp=0012094108&partnerID=8YFLogxK

U2 - 10.1007/3-540-45749-6_39

DO - 10.1007/3-540-45749-6_39

M3 - Conference contribution

AN - SCOPUS:0012094108

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 424

EP - 435

BT - Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings

A2 - Möhring, Rolf

A2 - Raman, Rajeev

PB - Springer Verlag

T2 - 10th Annual European Symposium on Algorithms, ESA 2002

Y2 - 17 September 2002 through 21 September 2002

ER -