English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

On Dualization in Products of Forests

MPS-Authors
/persons/resource/persons44374

Elbassioni,  Khaled
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Elbassioni, K. (2002). On Dualization in Products of Forests. In H. Alt, & A. Ferreira (Eds.), STACS 2002 (pp. 142-153). Berlin: Springer.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0019-EC4F-5
Abstract
Let \mathcalP}=\mathcal{P}_1×\ldots×\mathcal{P}_n 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 \mathcal{A}\subseteq\mathcal{P}, it is shown that the set of maximal independent elements of \mathcal{A} in \mathcal{P can be incrementally generated in quasi-polynomial time. We discuss some applications in data mining related to this dualization problem.