کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6423496 1342396 2011 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
When linear and weak discrepancy are equal
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
When linear and weak discrepancy are equal
چکیده انگلیسی

The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable, then |hL(x)−hL(y)|≤k, whereas the weak discrepancy is the least k such that there is a weak extension W of P such that if x and y are incomparable, then |hW(x)−hW(y)|≤k. This paper resolves a question of Tanenbaum, Trenk, and Fishburn on characterizing when the weak and linear discrepancy of a poset are equal. Although it is shown that determining whether a poset has equal weak and linear discrepancy is NP-complete, this paper provides a complete characterization of the minimal posets with equal weak and linear discrepancy. Further, these minimal posets can be completely described as a family of interval orders.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 311, Issue 4, 28 February 2011, Pages 252-257
نویسندگان
, ,