David Eppstein - Publications

To appear with unknown date

• All maximal independent sets and dynamic dominance for sparse graphs.
  D. Eppstein.
  arXiv:cs.DS/0407036.
  16th ACM-SIAM Symp. Discrete Algorithms, Vancouver, 2005, pp. 451-459.
  ACM Trans. Algorithms, to appear.

  We show how to apply reverse search to list all maximal independent sets in bounded-degree graphs in constant time per set, in graphs from minor closed families in linear time per set, and in sparse graphs in subquadratic time per set. The latter two results rely on new data structures for maintaining a dynamic vertex set in a graph and quickly testing whether the set dominates all other vertices.

  (SODA05 talk slides -- BibTeX)

• Space-Efficient Straggler Identification in Round-Trip Data Streams via Newton's Identitities and Invertible Bloom Filters.
  D. Eppstein, and M. T. Goodrich.
  10th Worksh. Algorithms and Data Structures, Halifax, Nova Scotia, 2007.
  Lecture Notes in Comp. Sci. 4619, 2007, pp. 637-648, © Springer-Verlag.
  arXiv:0704.3313.
  IEEE Trans. Knowledge and Data Engineering, to appear.

  We consider data structures for handling streams of check-in and check-out requests, and that must identify the set of check-ins that are not matched by a corresponding check-out. We show that, if this set has size k, it is possible to handle this problem in space O(k log n) by a deterministic data structure. However, if check-outs may occur that do not match any check-in, then no low-space deterministic solution is possible; instead, we provide a randomized solution with near-optimal space and high probability of answering queries correctly.

  (WADS talk slides)

Years -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine

Semi-automatically filtered from a common source file.