Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6872423 | Discrete Applied Mathematics | 2014 | 19 Pages |
Abstract
The main part of the paper is devoted to closure systems with unique critical sets, and some subclasses of these where the K-basis is unique. A further refinement in the form of the E-basis is possible for closure systems without D-cycles. There is a polynomial algorithm to recognize the D-relation from a K-basis. Consequently, closure systems without D-cycles can be effectively recognized. While the E-basis achieves an optimum in one of its parts, the optimization of the others is an NP-complete problem.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
K. Adaricheva, J.B. Nation,