Study of a combinatorial game in graphs through linear programming

DOI10.1007/s00453-018-0503-9zbMath1437.91112OpenAlexW2752259316MaRDI QIDQ1986957

Nicolas Nisse, Nathann Cohen, Stéphane Pérennes, Fionn Mc Inerney

Publication date: 9 April 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8225/

zbMATH Keywords

treelinear programminggraphsdominationgridcops and robber gamesspy game

Mathematics Subject Classification ID

Linear programming (90C05) Games involving graphs (91A43) Combinatorial games (91A46) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (5)

Eternal domination: \(D\)-dimensional Cartesian and strong grids and everything in between ⋮ Spy game: FPT-algorithm, hardness and graph products ⋮ Spy game: FPT-algorithm and results on graph products ⋮ The game of cops and eternal robbers ⋮ A method for eternally dominating strong grids

Cites Work

• \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
• Cops and robbers from a distance
• A game of cops and robbers
• Spy-game on graphs: complexity and simple topologies
• Vertex-to-vertex pursuit in a graph
• Cops and robbers is EXPTIME-complete
• Pursuing a fast robber on a graph
• Eternally dominating large grids
• Catching a fast robber on the grid
• To satisfy impatient web surfers is hard
• Connected Surveillance Game
• A Bound for the Cops and Robbers Problem
• The Domination Number of Grids
• Memoryless Determinacy of Parity Games
• The Cops and Robber game on graphs with forbidden (induced) subgraphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Study of a combinatorial game in graphs through linear programming