کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418898 681724 2008 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Edge ranking and searching in partial orders
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Edge ranking and searching in partial orders
چکیده انگلیسی

We consider a problem of searching an element in a partially ordered set (poset). The goal is to find a search strategy which minimizes the number of comparisons. Ben-Asher, Farchi and Newman considered a special case where the partial order has the maximum element and the Hasse diagram is a tree (tree-like posets) and they gave an O(n4log3n)O(n4log3n)-time algorithm for finding an optimal search strategy for such a partial order. We show that this problem is equivalent to finding edge ranking of a simple tree corresponding to the Hasse diagram, which implies the existence of a linear-time algorithm for this problem.Then we study a more general problem, namely searching in any partial order with maximum element. We prove that such a generalization is hard, and we give an O(lognlog(logn))-approximate polynomial-time algorithm for this problem.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 13, 6 July 2008, Pages 2493–2500
نویسندگان
,