Exact and heuristic algorithms for Cograph Editing

W. Timothy J. White, Marcus Ludwig, Sebastian Böcker

We present a dynamic programming algorithm for optimally solving the Cograph Editing problem on an $n$-vertex graph that runs in $O(3^{n}n)$ time and uses $O(2^n)$ space. In this pr…