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
3 votes
Accepted

Name and complexity of a stone placement puzzle

8 votes
Accepted

6-regular graph without small 3-regular subgraph

7 votes

What is this graph problem, and how hard is it?

10 votes
Accepted

Polynomial time solvable in series parallel graph but NP-hard in graph with bounded treewidth

5 votes

Do Knuth-Morris-Pratt and Booth’s LCS algorithm work in linear time on lists of lists of integers?

4 votes

Is there a standard axiomatization of graph width parameters?

5 votes
Accepted

Are there an algorithm that find Minimum spanning tree in $O(n^2\log\log^*n)$?

3 votes

Relationship between Random Graph Theory and TCS

1 vote

Planar 4-regular vertex-transitive graphs as system of circles

11 votes
Accepted

Finding vertex separator such that the induced subgraph has minimal number of edges

5 votes
Accepted

Complexity of relaxed edge colouring

9 votes

NP-Complete problems that admit an efficient algorithm under the promise of a unique solution

4 votes

Partitioning a connected polygon into connected pieces of equal area

5 votes
Accepted

Are there non trivial 2-basis of a 2-connected planar graph?

8 votes

What are some algorithms where space complexity tends to be the limiting factor in practice?

3 votes
Accepted

3-colourability of Eulerian maximal planar graph

2 votes

What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem?

16 votes

In the neutral zone between polynomial and sub-exponential

17 votes
Accepted

Number of connected components of a random nearest neighbor graph?

4 votes

Producing colouring of maximal planar graphs G from colouring of dual of G

7 votes
Accepted

On the complexity of a "list" datastructure in the RAM model

8 votes
Accepted

NP-completeness: sum of "some" paths in a spanning tree

5 votes

NP-complete decision problems on deterministic automata

7 votes
Accepted

On the coloring number of small graphs with small cliques

3 votes
Accepted

the shorstest cycle containing two given points

3 votes
Accepted

Convex polygons inclusion relation

3 votes
Accepted

The decision procedure of theory of closed real field is in NP-hard?

3 votes

Induction on all polynomial runtimes?

4 votes
Accepted

Diameter vs. Tractability

4 votes
Accepted

Longest stack-sortable subsequence

1
2 3 4 5
15