David Eppstein - Publications

Publications with Darren Strash

• Linear-time algorithms for geometric graphs with sublinearly many crossings.
  D. Eppstein, M. T. Goodrich, and D. Strash.
  arXiv:0812.0893.
  20th ACM-SIAM Symp. Discrete Algorithms, New York, 2009, pp. 150–159.
  SIAM J. Computing 39 (8): 3814–3829, 2010.

  If a connected graph corresponds to a set of points and line segments in the plane, in such a way that the number of crossing pairs of line segments is sublinear in the size of the graph by an iterated-log factor, then we can find the arrangement of the segments in linear time. It was previously known how to find the arrangement in linear time when the number of crossings is superlinear by an iterated-log factor, so the only remaining open case is when the number of crossings is close to the size of the graph.

• Listing all maximal cliques in sparse graphs in near-optimal time.
  D. Eppstein, M. Löffler, and D. Strash.
  arXiv:1006.5440.
  Workshop on Exact Algorithms for NP-Hard Problems, Dagstuhl, Germany, 2010.
  Proc. 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, 2010.
  Springer, Lecture Notes in Comp. Sci. 6506, 2010, pp. 403–414.
  

  We describe an algorithm for finding all maximal cliques in a graph, in time O(dn3^d/3) where n is the number of vertices and d is the degeneracy of the graph, a standard measure of its sparsity. This time bound matches the worst-case output size for these parameters. The algorithm modifies the Bron-Kerbosch algorithm for maximal cliques by ordering the vertices by degree in the outer recursive call of the algorithm.

  For the journal version, see "Listing all maximal cliques in large sparse real-world graphs," which combines results from this and a different conference paper.

• 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.
  Springer, Lecture Notes in Comp. Sci. 6508, 2010, pp. 128–141.
  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.

• Listing all maximal cliques in large sparse real-world graphs.
  D. Eppstein and D. Strash.
  10th Int. Symp. Experimental Algorithms, Crete, 2011.
  Springer, Lecture Notes in Comp. Sci. 6630, 2011, pp. 364–375.
  arXiv:1103.0318.

  We experiment with our degeneracy-based algorithm for listing maximal cliques in sparse graphs and show that it works well on large graphs drawn from several repositories of real-world social networks and bioinformatics networks.

  For the journal version, see "Listing all maximal cliques in large sparse real-world graphs", which combines results from this and a different conference paper.

• Category-based routing in social networks: membership dimension and the small-world phenomenon.
  D. Eppstein, M. T. Goodrich, M. Löffler, D. Strash, and L. Trott.
  Workshop on Graph Algorithms and Applications, Zürich, Switzerland, July 2011.
  International Conference on Computational Aspects of Social Networks (CASoN 2011), Salamanca, Spain, October 2011.
  arXiv:1108.4675.
  Theor. Comput. Sci. 514: 96–104, 2013. (Special issue on Graph Algorithms and Applications: in Honor of Professor Giorgio Ausiello)
  

  We investigate greedy routing schemes for social networks, in which participants know categorical information about some other participants and use it to guide message delivery by forwarding messages to neighbors that have more categories in common with the eventual destination. We define the membership dimension of such a scheme to be the maximum number of categories that any individual belongs to, a natural measure of the cognitive load of greedy routing on its participants. And we show that membership dimension is closely related to the small world phenomenon: a social network can be given a category system with polylogarithmic membership dimension that supports greedy routing if, and only if, the network has polylogarithmic diameter.

• Listing all maximal cliques in large sparse real-world graphs.
  D. Eppstein, M. Löffler, and D. Strash.
  J. Experimental Algorithmics 18 (3): 3.1, 2013 (special issue for SEA).

  This paper combines our theoretical results on clique-finding algorithms from ISAAC 2010 with our experimental results on the same algorithms from SEA 2011. We show how to list all maximal cliques in graphs of bounded degeneracy in time that is linear in the size of the graph and near-optimal in the degeneracy, and we show that low degeneracy explains the good behavior of the algorithm in our experiments on large real-world social networks.