Weak Positional Games on Hypergraphs of Rank Three

Kutz, Martin; Felsner, Stefan

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Weak Positional Games on Hypergraphs of Rank Three

MPS-Authors

/persons/resource/persons44874

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

Citation

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

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.