Before revision:  In the second case, the amortized update time is 2^{{\cal O}(k^4)} + }{\cal   .
After revision:  In the second case, the amortized update time is 2^{{\cal O}(k^4)} + }{\cal (k \log n). In both cases we assume access to a dictionary on the edges of G .