QP-2012-01

PPAD-completeness of polyhedral versions of Sperner's Lemma (Revised and extended version: TR-2012-04)

Tamás Király, Júlia Pap



Abstract

We prove that some polyhedral versions of Sperner's Lemma, where the colouring is explicitly given in the input, are PPAD-complete.


Bibtex entry:

@techreport{egresqp-12-01,
AUTHOR = {Kir{\'a}ly, Tam{\'a}s and Pap, J{\'u}lia},
TITLE = {PPAD-completeness of polyhedral versions of Sperner's Lemma (Revised and extended version: TR-2012-04)},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2012},
NUMBER = {QP-2012-01}
}


Last modification: 29.12.2019. Please email your comments to Tamás Király!