I assume the previous version must be retained in its entirety?
As I said in the post, "as best I could tell". I didn't see any way to avoid having to do so, although it's possible that a way might have existed and I failed to spot it.
I noted your saying that a graph couldn't be reduced in situ; I was just wanting confirmation that you can't delete graphn once you've made graphn+1, i.e. that you have to retain the entire sequence of graphs in order to reconstruct the colouring once all the reductions have been done.
Incidentally, if — as I suspect — the algorithm works by creating a reducing sequence of graphs then reconstructing a colouring back up the sequence towards the original, you can probably transform the algorithm from O(N2) time O(N2) space into one that's O(N3) time and O(N) space, simply by making sure the reduction sequence is deterministic then replaying it at each step in the reconstruction instead of using retained copies of the graphs.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
As I said in the post, "as best I could tell". I didn't see any way to avoid having to do so, although it's possible that a way might have existed and I failed to spot it.
I noted your saying that a graph couldn't be reduced in situ; I was just wanting confirmation that you can't delete graphn once you've made graphn+1, i.e. that you have to retain the entire sequence of graphs in order to reconstruct the colouring once all the reductions have been done.
Incidentally, if — as I suspect — the algorithm works by creating a reducing sequence of graphs then reconstructing a colouring back up the sequence towards the original, you can probably transform the algorithm from O(N2) time O(N2) space into one that's O(N3) time and O(N) space, simply by making sure the reduction sequence is deterministic then replaying it at each step in the reconstruction instead of using retained copies of the graphs.