This set of lecture notes describes a data structure for decremental connectivity in path graphs that supports queries and removals in amortized O(1) each. Has there been any work done on incremental connectivity on path graphs? Using a disjoint-set forest it's possible to do queries and insertions in amortized O(α(n)) time each, but can that be sped up using the fact that we're only looking at a path graph, not a general graph?


  • $\begingroup$ If you are given the sequence of vertices $v_1,\ldots,v_n$, and you can only add edges between $v_i$ and $v_{i+1}$, then $O(1)$ time seems possible. Otherwise maybe modifying the lower bound for disjoint-set data structure can get you the lower bound. $\endgroup$ – Chao Xu Jan 20 '16 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.