The largest connected subgraph game

DOI10.1007/s00453-022-00973-5OpenAlexW3158936983MaRDI QIDQ5918781

Julien Bensmail, Fionn Mc Inerney, Nicolas Nisse, Foivos Fioravantes

Publication date: 18 August 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-022-00973-5

zbMATH Keywords

games on graphsPSPACE-completeconnection gamesGI-hardscoring games

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (4)

The maker-breaker largest connected subgraph game ⋮ Smash and grab: the \(0 \cdot 6\) scoring game on graphs ⋮ Bipartite instances of INFLUENCE ⋮ The complexity of two colouring games

Cites Work

• Unnamed Item
• On the complexity of connection games
• Guaranteed scoring games
• Occupation games on graphs in which the second player takes almost all vertices
• Hex ist Pspace-vollständig. (Hex is Pspace-complete)
• On the complexity of some two-person perfect-information games
• Game comparison through play
• The median game
• Games with guaranteed scores and waiting moves
• \textsc{influence}: a partizan scoring game on graphs
• The orthogonal colouring game
• A Linear Recognition Algorithm for Cographs
• A Combinatorial Problem Which Is Complete in Polynomial Space
• A Graph-Grabbing Game
• The largest connected subgraph game

This page was built for publication: The largest connected subgraph game