**Parallel algorithmic techniques for combinatorial computation**.

D. Eppstein and Z. Galil.

*Ann. Rev. Comput. Sci.*3: 233–283, 1988.

Invited talk by Z. Galil,*16th Int. Coll. Automata, Languages and Programming,*Stresa, Italy, 1989.

Springer,*Lecture Notes in Comp. Sci.*372, 1989, pp. 304–318.This survey on parallel algorithms emphasized the use of basic subroutines such as prefix sums, Euler tours, ear decomposition, and matrix multiplication for solving more complicated graph problems.

(BibTeX – Citations – CiteSeer – ACM DL (ARCS) – ACM DL (ICALP))

**Efficient sequential and parallel algorithms for computing recovery points in trees and paths**.

M. Chrobak, D. Eppstein, G.F. Italiano, and M. Yung.

*2nd ACM-SIAM Symp. Discrete Algorithms,*San Francisco, 1991, pp. 158–167.

ALCOM Report 91-74, University of Rome, 1991.Described slightly superlinear algorithms for partitioning a tree into a given number of subtrees, making them all as short as possible. Frederickson at the same conference further improved the sequential time to linear. There may still be something worth publishing in the parallel algorithms.

**Clustering for faster network simplex pivots**.

D. Eppstein.

Tech. Rep. 93-19, ICS, UCI, 1993.

*5th ACM-SIAM Symp. Discrete Algorithms,*Arlington, 1994, pp. 160–166.

*Networks*35 (3): 173–180, 2000.Speeds up the worst case time per pivot for various versions of the network simplex algorithm for minimum cost flow problems. Uses techniques from dynamic graph algorithms as well as some simple geometric data structures.

**Minimum range balanced cuts via dynamic subset sums**.

D. Eppstein.

Tech. Rep. 95-10, ICS, UCI, 1995.

*J. Algorithms*23: 375–385, 1997.Describes data structures for maintaining the solution of a dynamically changing subset sum problem, and uses them to find a cut in a graph minimizing the difference between the heaviest and lightest cut edge.

**The weighted maximum-mean subtree and other bicriterion subtree problems.**

J. Carlson and D. Eppstein.

arXiv:cs.CG/0503023.

*Proc. 10th Scand. Worksh. Algorithm Theory (SWAT 2006)*.

Springer,*Lecture Notes in Comp. Sci.*4059, 2006, pp. 397–408.We give a linear time algorithm for pruning a node-weighted tree to maximize the average node weight of the pruned subtree; this problem was previously studied under the less obvious name "The Fractional Prize-Collecting Steiner Tree Problem on Trees".

(BibTeX)

**Interconnect criticality driven delay relaxation.**

L. Singhal, E. Bozorgzadeh, and D. Eppstein.

*IEEE Trans. CAD*26 (10): 1803–1817, 2007.We consider a problem of assigning delays to components in a circuit so that each component is part of a critical path, but the number of edges belonging to critical paths is minimized. We show the problem to be NP-complete via a reduction from finding independent dominating sets in bipartite graphs minimizing dominated edges, and give experimental results on heuristics.

**Graph-theoretic solutions to computational geometry problems**.

D. Eppstein.

Invited talk at the 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), Montpellier, France, 2009.

Springer,*Lecture Notes in Comp. Sci.*5911, 2009, pp. 1–16.

arXiv:0908.3916.We survey problems in computational geometry that may be solved by constructing an auxiliary graph from the problem and solving a graph-theoretic problem on the auxiliary graph. The problems considered include the art gallery problem, partitioning into rectangles, minimum diameter clustering, bend minimization in cartogram construction, mesh stripification, optimal angular resolution, and metric embedding.

**Going off-road: transversal complexity in road networks**.

D. Eppstein, M. T. Goodrich, and L. Trott.

arXiv:0909.2891.

Proc. 17th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems, Seattle, 2009, pp. 23–32.Shows both theoretically and experimentally that the number of times a random line crosses a road network is asymptotically upper bounded by the square root of the number of road segments.

**Paired approximation problems and incompatible inapproximabilities**.

D. Eppstein.

arXiv:0909.1870.

*21st ACM-SIAM Symp. Discrete Algorithms*, Austin, Texas, 2010, pp. 1076–1086.Considers situations in which two hard approximation problems are presented by means of a single input. In many cases it is possible to guarantee that one or the other problem can be approximated to within a better approximation ratio than is possible for approximating it as a single problem. For instance, it is possible to find either a (1+ε)-approximation to a 1-2 TSP defined from a graph or a n

^{ε}-approximation to the maximum independent set of the same graph, despite lower bounds showing nonexistence of approximation schemes for 1-2 TSP and nonexistence of approximations better than n^{1 − ε}for independent set. However, for some other pairs of problems, such as hitting set and set cover, we show that solving the paired problem approximately is no easier than solving either problem independently.(Slides)

**Windows into relational events: data structures for contiguous subsequences of edges**.

M. J. Bannister, C. DuBois, D. Eppstein, and P. Smyth.

*NIPS 2012 Workshop on Algorithmic and Statistical Approaches for Large Social Networks*, South Lake Tahoe, California, 2012 (poster and invited talk).

*24th ACM-SIAM Symp. Discrete Algorithms*, New Orleans, Louisiana, 2013, pp. 856–864.

arXiv:1209.5791.We study relational event data in which a collection of actors in a social network have a sequence of pairwise interactions. Contiguous subsequences of these interactions form graphs, and we develop efficient data structures for querying the parameters of these graphs.

**Grid minors in damaged grids**.

D. Eppstein.

arXiv:1303.1136.

*Electronic J. Combinatorics*21(3), Paper P3.20, 2014.We give tight bounds on the size of the largest remaining grid minor in a grid graph from which a given number of vertices have been deleted, and study several related problems.

**Automated generation of linkage loop equations for planar 1-dof linkages, demonstrated up to 8-bar**.

B. E. Parrish, J. M. McCarthy, and D. Eppstein.

*Proc. ASME 2014 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference*, Vol. 5A:*38th Mechanisms and Robotics Conference*, Buffalo, New York, USA, August 17-20, 2014, paper no. DETC2014-35263.

*J. Mechanisms and Robotics*7 (1): 011006, 2015.This paper reports on an implementation of an algorithm for constructing the configuration space of two-dimensional linkages with one degree of freedom.

(eScholarship conference version – eScholarship journal version)

**ERGMs are hard**.

M. J. Bannister, W. E. Devanny, and D. Eppstein.

arXiv:1412.1787.

ERGMs (exponential random graph models) are used in social science to describe probability distributions on graphs that are supposed to mimic real-world social networks. However, we show that (with features that are standard in the social science application) the distributions given by these models can be computationally infeasible to sample from or to approximate the probability of seeing a given graph.

**Metric dimension parameterized by max leaf number**.

D. Eppstein.

arXiv:1506.01749.

*J. Graph Algorithms & Applications*19 (1): 313–323, 2015.We prove that when a graph of bounded size has its edges subdivided to form a larger graph, it is still possible to find its metric dimension by a fixed-parameter tractable algorithm, parameterized by the pre-subdivision size of the graph.

**The computational hardness of**.*d*K-series

W. E. Devanny, D. Eppstein, and B. Tilman.

*NetSci2016*poster session, Seoul, Korea.The

*d*K-series is an extension of the degree sequence of a graph to a*d*-dimensional tensor, describing the number of*d*-tuples of vertices with each possible combination of degrees and adjacencies. As we show, it is NP-hard to determine whether such a tensor represents a valid graph, for any*d*≥ 3, or for*d*= 2 if the number of triangles in the graph is also specified (or constrained to be zero).**Models and algorithms for graph watermarking**.

D. Eppstein, M. T. Goodrich, J. Lam, N. Mamano, M. Mitzenmacher, and M. Torres.

arXiv:1605.09425.

*Proc. 19th Information Security Conference (ISC 2016)*, Honolulu, Hawaii.

Springer,*Lecture Notes in Comp. Sci.*9866 (2016), pp. 283–301.We show how to modify a small number of edges in a large social network in order to make the modified copy easy to identify, even if an adversary tries to hide the modification by permuting the vertices and flipping a much larger number of edges. The result depends on the random fluctuation of vertex degrees in such networks, and the ability to uniquely identify vertices by their adjacencies to a small number of high-degree landmark vertices. This paper won the best student paper award at ISC for its student co-authors Lam, Mamano, and Torres.

Graph Theory – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.