An algorithm for dualization in products of lattices and its applications

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

10 Scopus citations

Abstract

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.

Original languageBritish English
Title of host publicationAlgorithms - ESA 2002 - 10th Annual European Symposium, Proceedings
EditorsRolf Möhring, Rajeev Raman
PublisherSpringer Verlag
Pages424-435
Number of pages12
ISBN (Electronic)3540441808, 9783540441809
DOIs
StatePublished - 2002
Event10th Annual European Symposium on Algorithms, ESA 2002 - Rome, Italy
Duration: 17 Sep 200221 Sep 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2461
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th Annual European Symposium on Algorithms, ESA 2002
Country/TerritoryItaly
CityRome
Period17/09/0221/09/02

Fingerprint

Dive into the research topics of 'An algorithm for dualization in products of lattices and its applications'. Together they form a unique fingerprint.

Cite this