David Eppstein - Publications

Publications with S. Muthukrishnan

• Internet packet filter management and rectangle geometry.
  D. Eppstein and S. Muthukrishnan.
  arXiv:cs.CG/0010018.
  12th ACM-SIAM Symp. Discrete Algorithms, Washington, 2001, pp. 827-835.

  Rule sets for internet routers and firewalls can be represented as sets of prioritized rectangles; the rule to use for a packet is the maximum priority rectangle containing its (source,destination) address pair. We develop efficient data structures for performing these queries, and find an O(n^3/2) time algorithm for testing whether a rule set contains any ambiguities.

  (BibTeX -- Citations -- SODA paper -- CiteSeer)

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

Semi-automatically filtered from a common source file.