Skip to Main content Skip to Navigation
Conference papers

Weak Positional Games on Hypergraphs of Rank Three

Abstract : 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.
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184379
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 17, 2015 - 8:42:57 AM
Last modification on : Thursday, September 20, 2018 - 7:54:02 AM
Long-term archiving on: : Wednesday, November 18, 2015 - 10:34:53 AM

File

dmAE0107.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184379, version 1

Collections

Citation

Martin Kutz. Weak Positional Games on Hypergraphs of Rank Three. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.31-36. ⟨hal-01184379⟩

Share

Metrics

Record views

719

Files downloads

729