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 \(K_3\) or \(K_4\). More recently this paper has been cited for its applications to scheduling update operations in parallel finite element methods.
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.
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.
Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect.
J. Cardinal, E. Demaine, D. Eppstein, R. Hearn, and A. Winslow.
arXiv:1805.04055
Proc. 24th International Computing and Combinatorics Conference (COCOON 2018), Qingdao, China.
Springer, Lecture Notes in Comp. Sci. 10976 (2018), pp. 365–377.
Theor. Comput. Sci. 806: 332–343, 2020.For several problems with polynomial-time solutions, we show that finding a sequence of steps that converts one solution into another (maintaining a valid solution at each step) is hard. These include planar monotone not-all-equal 3-sat, subset sum on integers of polynomial magnitude, and 0-1 integer programming with a constant number of linear inequality constraints.
On the treewidth of Hanoi graphs.
D. Eppstein, D. Frishberg, and W. Maxwell.
arXiv:2005.00179.
Proc. 10th Int. Conf. Fun with Algorithms (FUN 2021).
Leibniz International Proceedings in Informatics (LIPIcs) 157, 2020, pp. 13:1–13:21.
Theor. Comput. Sci. 906: 1–17, 2022.The n-disc p-peg Hanoi graphs have treewidth within a polynomial factor of np − 1.