Open AccessOn Dualization in Products of Forests
Author(s) -
Khaled Elbassioni
Publication year - 2002
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
ISBN - 3-540-43283-3
DOI - 10.1007/3-540-45841-7_11
Subject(s) - computer science , bounded function , degree (music) , graph , product (mathematics) , set (abstract data type) , discrete mathematics , combinatorics , algorithm , theoretical computer science , mathematics , programming language , mathematical analysis , physics , geometry , acoustics
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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom