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.
Type de document :
Communication dans un congrès
Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.31-36, 2005, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01184379
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 17 août 2015 - 08:42:57
Dernière modification le : jeudi 20 septembre 2018 - 07:54:02
Document(s) archivé(s) le : mercredi 18 novembre 2015 - 10:34:53

Fichier

dmAE0107.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184379, version 1

Collections

Citation

Martin Kutz. Weak Positional Games on Hypergraphs of Rank Three. Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.31-36, 2005, DMTCS Proceedings. 〈hal-01184379〉

Partager

Métriques

Consultations de la notice

217

Téléchargements de fichiers

208