David Eppstein

Irvine, California

http://www.ics.uci.edu/~eppstein/

I'm a professor of computer science at the University of California, Irvine, working on graph algorithms and computational geometry.

top accounts reputation activity subscriptions

Positive topological ordering

ds.algorithms directed-acyclic-graph partial-order topological-sorting asked Sep 16, 2010 at 1:24

cstheory.stackexchange.com

39 votes

How many distinct colors are needed to lower-bound the choosability of a graph?

graph-theory co.combinatorics graph-colouring exp-time-algorithms asked Nov 2, 2010 at 18:58

cstheory.stackexchange.com

27 votes

Ax–Grothendieck and the Garden of Eden

ag.algebraic-geometry cellular-automata asked Mar 18, 2011 at 6:13

mathoverflow.net

26 votes

Rabin–Karp vs Karp–Rabin

ho.history-overview string-matching asked May 14, 2014 at 4:42

cstheory.stackexchange.com

26 votes

Hamiltonicity of k-regular graphs

graph-theory np-hardness hamiltonian-paths asked Sep 24, 2010 at 21:33

cstheory.stackexchange.com

25 votes

Random self-avoiding lattice cycle within a given bounding box

ds.algorithms randomness markov-chains integer-lattice asked Mar 12, 2011 at 4:24

cstheory.stackexchange.com

22 votes

Splittable stack

ds.data-structures asked Apr 7, 2011 at 1:26

cstheory.stackexchange.com

21 votes

Approximate 1d TSP with linear comparisons?

ds.algorithms approximation-algorithms sorting tsp asked Sep 12, 2012 at 22:44

cstheory.stackexchange.com

21 votes

Triangle centers from curve shortening

dg.differential-geometry triangles asked Nov 2, 2015 at 4:21

mathoverflow.net

20 votes

Complexity of finding the smallest well-covered completion

cc.complexity-theory graph-algorithms asked Aug 12, 2011 at 22:42

cstheory.stackexchange.com

Top Answers

162

Are research papers hard to read?

cstheory.stackexchange.com

MathSciNet vs Google Scholar

mathoverflow.net

Is it possible to capture a sphere in a knot?

mathoverflow.net

One Stack, Two Queues

cstheory.stackexchange.com

Problems Between P and NPC

cstheory.stackexchange.com

Are there any open problems left about DFAs?

cstheory.stackexchange.com

Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$

cstheory.stackexchange.com

Counting words accepted by a regular grammar

cstheory.stackexchange.com

NP-hard problems on trees

cstheory.stackexchange.com

Magic constant to solve NP-complete problem in polynomial time

cstheory.stackexchange.com

Graph containing all trees?

mathoverflow.net

How are real numbers specified in computation?

cstheory.stackexchange.com

Nontrivial algorithm for computing a sliding window median

cstheory.stackexchange.com

Fundamental Examples

mathoverflow.net

Algorithm for finding the volume of a convex polytope

mathoverflow.net

A game of stones

mathoverflow.net

Why would one ever use an Octree over a KD-tree?

cstheory.stackexchange.com

Polynomial Time Algorithm for Graph Isomorphism Testing

cstheory.stackexchange.com

The origin of the notion of treewidth

cstheory.stackexchange.com

Geometric problems that are NP-complete in $R^3$ but tractable in $R^2$?

cstheory.stackexchange.com

A probabilistic set with no false positives?

cstheory.stackexchange.com

Is DAG isomorphism NP-C

cstheory.stackexchange.com

Is there a problem that is easy for cubic graphs but hard for graphs with maximum degree 3?

cstheory.stackexchange.com

Is it a rule that discrete problems are NP-hard and continuous problems are not?

cstheory.stackexchange.com

Example where equivalence is easy but finding class representative is hard

cstheory.stackexchange.com

Finding k shortest Paths with Eppstein's Algorithm

cstheory.stackexchange.com

Best-case Running-time to solve an NP-Complete problem

mathoverflow.net

What universities have laid off tenured math faculty for financial reasons?

mathoverflow.net

Counting the number of Hamiltonian cycles in cubic Hamiltonian graphs?

cstheory.stackexchange.com

Is any chordal graph an incomparability graph?

cstheory.stackexchange.com