Minimal elements of a poset
- From: Jens Auer <jens.auer-news@xxxxxxxxxxxxxxx>
- Date: Wed, 15 Feb 2006 12:59:48 +0100
Hi,
I have a set of finite sets over the fixed domain {1...n}, eg { {1}, {1,2}, {1,3}, {2} }. In the algorithm I am implementing, the most time-consuming step is to compute all minimal elements wrt to the subset relation. My current implementation uses a quadratic algorithm together with some heuristics, but for large sets, this becomes very inefficient.
Does anybody know any efficient algorithm (or a proven lower bound for complexity) for this problem?
.
- Prev by Date: Re: languages
- Next by Date: Re: languages
- Previous by thread: probability of where a random element goes when inserted into an already sorted list?
- Next by thread: Books on Computer Theory
- Index(es):