Dynamic connectivity in digital images

David Eppstein
Information Processing Letters 62(3):121–126, May 1997
Tech. report 96-13, Univ. of California, Irvine, Dept. of Information and Computer Science, 1996
http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-13.pdf

Cited by:

• Lower bounds for fully dynamic connectivity problems in graphs
• Searching constant width mazes captures the AC$^0$-hierarchy
• Hardness results for dynamic problems by extensions of Fredman and Saks' chronogram method
• Cell probe complexity — a survey
• New lower bound techniques for dynamic partial sums and related problems