\(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma

DOI10.1016/j.disc.2013.04.006zbMath1279.05026OpenAlexW2053906565WikidataQ124798876 ScholiaQ124798876MaRDI QIDQ389197

Júlia Pap, Tamás Király

Publication date: 17 January 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2013.04.006

zbMATH Keywords

computational complexityvertex covercolouring of polyhedra

Mathematics Subject Classification ID

Combinatorial aspects of finite geometries (05B25) Coloring of graphs and hypergraphs (05C15)

Related Items (2)

Colorful linear programming, Nash equilibrium, and pivots ⋮ Envy-free cake division without assuming the players prefer nonempty pieces

Cites Work

• Unnamed Item
• A note on kernels and Sperner's Lemma
• On the complexity of the parity argument and other inefficient proofs of existence
• On the \(\epsilon\)-perturbation method for avoiding degeneracy
• The complexity of computing a Nash equilibrium
• Maximum-Minimum Sätze über Graphen
• Settling the complexity of computing two-player Nash equilibria
• On the Complexity of 2D Discrete Fixed Point Problem
• Reducibility among Fractional Stability Problems
• The Core of an N Person Game

This page was built for publication: \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma