Complexity of maker-breaker games on edge sets of graphs
From MaRDI portal
Publication:6657252
DOI10.1016/j.dam.2024.11.012MaRDI QIDQ6657252
Valentin Gledel, Miloš Stojaković, Nacim Oijid, Fionn Mc Inerney, Nicolas Nisse, Eric Duchêne, Aline Parreau
Publication date: 6 January 2025
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
computational complexitymaker-breaker gamesperfect matching game\( \mathsf{FPT} \)\( \mathsf{PSPACE} \)-hard\(H\)-game
Cites Work
- On the complexity of connection games
- Fundamentals of parameterized complexity
- Winning strong games through fast strategies for weak games
- Parameterized pursuit-evasion games
- Maker-Breaker domination game
- On two problems regarding the Hamiltonian cycle game
- Edge-disjoint spanning trees and depth-first search
- On the complexity of some two-person perfect-information games
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
- Odd and even cycles in maker-breaker games
- Positional games
- Fast winning strategies in maker-breaker games
- On representatives of subsets.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The maker-breaker largest connected subgraph game
- On the threshold for the Maker-BreakerH-game
- On the Complexity of Chooser–Picker Positional Games
- A threshold for the Maker-Breaker clique game
- Asymptotic random graph intuition for the biased connectivity game
- The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
- Deciding first-order properties of locally tree-decomposable structures
- Parameterized Chess
- A sharp threshold for the Hamilton cycle Maker–Breaker game
- Remarks on positional games. I
- A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory
- A Combinatorial Problem Which Is Complete in Polynomial Space
- Biased Positional Games
- Graph Ramsey games
- Fast strategies in biased Maker--Breaker games
- Positional games on random graphs
- Twin-width I: Tractable FO Model Checking
- The Parameterized Complexity of Positional Games
- Combinatorial Games
- A Solution of the Shannon Switching Game
- On a combinatorial game
- Biased positional games for which random strategies are nearly optimal
- 6-uniform Maker-Breaker game is PSPACE-complete
- \((k-2)\)-linear connected components in hypergraphs of rank \(k\)
- Avoidance games are PSPACE-complete
This page was built for publication: Complexity of maker-breaker games on edge sets of graphs
