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

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 egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2012},
NUMBER	=	{QP-2012-01}

}