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
