کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647714 1342369 2013 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
PPAD-completeness of polyhedral versions of Sperner’s Lemma
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
PPAD-completeness of polyhedral versions of Sperner’s Lemma
چکیده انگلیسی

We show that certain polyhedral versions of Sperner’s Lemma, where the colouring is given explicitly as part of the input, are PPAD-complete. The proofs are based on two recent results on the complexity of computational problems in game theory: the PPAD-completeness of 2-player Nash, proved by Chen and Deng, and of Scarf’s Lemma, proved by Kintali. We give a strengthening of the latter result, show how colourings of polyhedra provide a link between the two, and discuss a special case related to vertex covers.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 313, Issue 15, 6 August 2013, Pages 1594–1599
نویسندگان
, ,