David Eppstein - Publications

Theoretical Computer Science

• Planar orientations with low out-degree and compaction of adjacency matrices.
  M. Chrobak and D. Eppstein.
  Theor. Comp. Sci. 86(2):243-266, 1991.

  Describes efficient sequential and parallel algorithms for orienting the edges of an undirected planar graph so that each vertex has few outgoing edges. From such an orientation one can test in constant time whether a given edge exists. One consequence is a parallel algorithm to list all subgraphs isomorphic to K3 or K4. More recently this paper has been cited for its applications to scheduling update operations in parallel finite element methods.

  (BibTeX -- Citations -- CiteSeer -- ACM DL)

• Extended dynamic subgraph statistics using h-index parameterized data structures.
  D. Eppstein, M. T. Goodrich, D. Strash, and L. Trott.
  Proc. 4th Int. Conf. on Combinatorial Optimization and Applications (COCOA 2010), Hawaii, 2010.
  Lecture Notes in Comp. Sci. 6508, 2010, pp. 128-141, Springer-Verlag.
  arXiv:1009.0783.
  Theor. Comput. Sci. 447: 44-52, 2012 (special issue for COCOA 2010).

  An earlier paper with Spiro at WADS 2009 provided dynamic graph algorithms for counting how many copies of each possible type of subgraph there are in a larger undirected graph, when the subgraphs have at most three vertices. This paper extends the method to directed graphs and to larger numbers of vertices per subgraph.

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

Semi-automatically filtered from a common source file.