David Eppstein

Home * People * David Eppstein

David Eppstein 1 David Eppstein ¹

David A. Eppstein,
an American mathematician and computer scientist. He is professor in the Computer Science Department, Donald Bren School of Information and Computer Sciences, University of California, Irvine. He received a B.Sc. in mathematics from Stanford University in 1984, and M.Sc. and Ph.D. degrees in computer science from Columbia University in 1985 and 1989 respectively. His research interests covers algorithms and data structures, complexity theory, graph theory, such as minimum spanning tree, shortest path, and graph coloring as well as game theory and finite element methods. He teaches strategy and board game programming and tried his own hands on Fanorona ¹, a traditional board game from Madagascar.

Contents

Selected Publications

Marshall Bern, David Eppstein (1995). Mesh Generation and Optimal Triangulation. Computing in Euclidean Geometry (2nd ed), pdf ⁵
David Eppstein (1997). Dynamic Connectivity in Digital Images. Information Processing Letters, Vol. 62, No. 3, TR-96-13.pdf
David Eppstein (1998). Finding the k Shortest Paths. SIAM Journal on Computing, Vol. 28, No. 2, pdf
David Eppstein (1999). Setting Parameters by Example. arXiv:cs/9907001

David Eppstein (2000). Searching for Spaceships. arXiv:cs/0004003
Erik D. Demaine, Martin L. Demaine, David Eppstein (2000). Phutball Endgames are Hard. arXiv:cs/0008025 ⁶
Cristopher Moore, David Eppstein (2000). One-Dimensional Peg Solitaire. arXiv:math/0006067 ⁷
Cristopher Moore, David Eppstein (2000). One-Dimensional Peg Solitaire, and Duotaire. arXiv:math/0008172
David Eppstein, S. Muthukrishnan (2000). Internet Packet Filter Management and Rectangle Geometry. arXiv:cs/0010018
David Eppstein, Jean-Claude Falmagne (2002). Algorithms for Media. arXiv:cs/0206033
David Eppstein (2004). Algorithms for Drawing Media. arXiv:cs/0406020
David Eppstein (2004). Quasiconvex Programming. arXiv:cs/0412046

David Eppstein, Michael T. Goodrich, Jonathan Z. Sun (2005). The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data. https://arxiv.org/abs/cs/050704
David Eppstein (2005). Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku. arXiv:cs/0507053
David Eppstein (2008). Learning Sequences. arXiv:0803.4030
David Eppstein, Jean-Claude Falmagne, Sergei Ovchinnikov (2008). Media Theory - interdisciplinary applied mathematics. Springer
David Eppstein (2009). Growth and Decay in Life-Like Cellular Automata. arXiv:0911.2890

Michael J. Bannister, David Eppstein (2011). Randomized Speedup of the Bellman-Ford Algorithm. arXiv:1111.5414 ⁸
David Eppstein (2012). Solving Single-digit Sudoku Subproblems. arXiv:1202.5074
David Eppstein, Michael T. Goodrich, Michael Mitzenmacher, Paweł Pszona (2014). Wear Minimization for Cuckoo Hashing: How Not to Throw a Lot of Eggs into One Basket. arXiv:1404.0286
Erik D. Demaine, David Eppstein, Adam Hesterberg, Hiro Ito, Anna Lubiw, Ryuhei Uehara, Yushi Uno (2014). Folding a Paper Strip to Minimize Thickness. arXiv:1411.6371

David Eppstein (2016). Cuckoo Filter: Simplification and Analysis. arXiv:1604.06067 ⁹
David Eppstein, Vijay V. Vazirani (2018). NC Algorithms for Perfect Matching and Maximum Flow in One-Crossing-Minor-Free Graphs. arXiv:1802.00084 ¹⁰
David Eppstein (2018). Faster Evaluation of Subtraction Games. arXiv:1804.06515
David Eppstein (2018). Making Change in 2048. arXiv:1804.07396
David Eppstein (2018). Forbidden Configurations in Discrete Geometry. Cambridge University Press
Erik D. Demaine, David Eppstein, Adam Hesterberg, Kshitij Jain, Anna Lubiw, Ryuhei Uehara, Yushi Uno (2019). Reconfiguring Undirected Paths. arXiv:1905.00518

Analyzing Algorithm X in honor of Knuth's 70th birthday, by David Eppstein, January 2008