On the Non-Locality of Edge Insertions

Florestan Brunck

We challenge the idea that edge insertions are local improvement operations and show that the edge-insertion algorithm must sometimes insert an edge between vertices that are at th…