David Eppstein's user avatar
David Eppstein's user avatar
David Eppstein's user avatar
David Eppstein
  • Member for 13 years, 8 months
  • Last seen more than a month ago
166 votes
Accepted

Are research papers hard to read?

48 votes
Accepted

One Stack, Two Queues

45 votes

Problems Between P and NPC

44 votes

Are there any open problems left about DFAs?

41 votes
Accepted

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

38 votes
Accepted

Counting words accepted by a regular grammar

36 votes

NP-hard problems on trees

34 votes

Magic constant to solve NP-complete problem in polynomial time

33 votes
Accepted

How are real numbers specified in computation?

32 votes
Accepted

Nontrivial algorithm for computing a sliding window median

30 votes

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

30 votes
Accepted

A probabilistic set with no false positives?

29 votes
Accepted

Polynomial Time Algorithm for Graph Isomorphism Testing

29 votes

The origin of the notion of treewidth

29 votes

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

27 votes
Accepted

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

27 votes
Accepted

Is DAG isomorphism NP-C

26 votes

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

25 votes

Example where equivalence is easy but finding class representative is hard

25 votes
Accepted

Partition a graph into node-disjoint cycles

25 votes
Accepted

Finding k shortest Paths with Eppstein's Algorithm

24 votes
Accepted

If an abstract machine can simulate itself, does that make it Turing complete?

24 votes
Accepted

What is the smallest result you publish on ArXiv?

24 votes
Accepted

Is any chordal graph an incomparability graph?

24 votes

Counting the number of Hamiltonian cycles in cubic Hamiltonian graphs?

23 votes

Examples of the price of abstraction?

23 votes
Accepted

Upper bounds on the length of longest simple path in non-Hamiltonian graph?

23 votes
Accepted

Is this graph transformation unique up to isomorphism? [Answer:NO]

23 votes

What is the enlightenment I'm supposed to attain after studying finite automata?

22 votes
Accepted

Golden ratio or Pi in the running time

1
2 3 4 5
15