Skip to main content
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
47 votes
5 answers
3k views

Positive topological ordering

39 votes
2 answers
1k views

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

28 votes
2 answers
4k views

Hamiltonicity of k-regular graphs

26 votes
1 answer
738 views

Rabin–Karp vs Karp–Rabin

25 votes
1 answer
778 views

Random self-avoiding lattice cycle within a given bounding box

22 votes
1 answer
968 views

Splittable stack

21 votes
1 answer
948 views

Approximate 1d TSP with linear comparisons?

20 votes
0 answers
589 views

Complexity of finding the smallest well-covered completion

19 votes
1 answer
733 views

Rapidly mixing Markov chains on 3-colorings of a cycle

18 votes
1 answer
1k views

Reference for mixed graph acyclicity testing algorithm?

17 votes
2 answers
527 views

Parameterized complexity of graph intersection number

14 votes
1 answer
4k views

Computing input length on a one-tape Turing machine

13 votes
0 answers
192 views

Name and references for balanced variant of the long code?

13 votes
1 answer
710 views

For which graphs is the DFS tree always a path?

12 votes
1 answer
519 views

Optimal randomized comparison sorting

6 votes
1 answer
346 views

Complexity of finding large grid minors