Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Conference Paper

Weak Positional Games on Hypergraphs of Rank Three


Kutz,  Martin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Kutz, M. (2005). Weak Positional Games on Hypergraphs of Rank Three. In 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (pp. 31-36). Nancy, France: DMTCS.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-283E-2
In a weak positional game, two players, Maker and Breaker, alternately claim vertices of a hypergraph until either Maker wins by getting a complete edge or all vertices are taken without this happening, a Breaker win. For the class of almost-disjoint hypergraphs of rank three (edges with up to three vertices only and edge-intersections on at most one vertex) we show how to find optimal strategies in polynomial time. Our result is based on a new type of decomposition theorem which might lead to a better understanding of weak positional games in general.