An Efficient Search Algorithm for Partially Ordered Sets

Yan Chen (PRC)


algorithms and computation theories, membership query, partial order, greedy algorithm


Consider the problem of membership query for a given par tially ordered set. We devise a greedy algorithm which can produce near-optimal search strategies. Rigorous analysis has been given, which shows our algorithm can have fewer comparisons than the best known solution by at least a fac tor of 0.27 under random graph model. Experimental re sults have also been given, which suggest the advantage of the algorithm under other models.

Important Links:

Go Back