On dualization in products of forests

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

6 Scopus citations

Abstract

Let P = Pi ×… × Pn be the product of n partially ordered sets, each with an acyclic precedence graph in which either the in-degree or the out-degree of each element is bounded. Given a subset A ⊆ P, it is shown that the set of maximal independent elements of A in P can be incrementally generated in quasi-polynomial time. We discuss some applications in data mining related to this dualization problem.

Original languageBritish English
Title of host publicationSTACS 2002 - 19th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
EditorsHelmut Alt, Afonso Ferreira
PublisherSpringer Verlag
Pages142-153
Number of pages12
ISBN (Electronic)9783540432838
DOIs
StatePublished - 2002
Event19th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2002 - Antibes - Juan les Pins, France
Duration: 14 Mar 200216 Mar 2002

Publication series

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

Conference

Conference19th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2002
Country/TerritoryFrance
CityAntibes - Juan les Pins
Period14/03/0216/03/02

Keywords

  • Data mining
  • Dualization
  • Forest
  • Incremental algorithms
  • Poset

Fingerprint

Dive into the research topics of 'On dualization in products of forests'. Together they form a unique fingerprint.

Cite this