Python package Cop-number: Checks whether the cop number of a NetworkX graph is greater than k. This is a python implementation of the algorithm described in The Game of Cops and Robbers on Graphs by Anthony Bonato to solve k-FIXED COP NUMBER. The time complexity of the algorithm is O(n^{3k + 3}). This implementation is very slow for k greater than about 5 for even moderately sized graphs with 30 - 40 vertices. Currently, input graphs are treated as reflexive. If they are not reflexive, then self edges are added.

Keywords for this software

Anything in here will be replaced on browsers that support the canvas element

References in zbMATH (referenced in 2 articles )

Showing results 1 to 2 of 2.
Sorted by year (citations)

  1. Turcotte, Jérémie: Cops and robbers on (2K_2)-free graphs (2022)
  2. Turcotte, Jérémie; Yvon, Samuel: 4-cop-win graphs have at least 19 vertices (2021)