Skip to main content
virgi's user avatar
virgi's user avatar
virgi's user avatar
virgi
  • Member for 13 years, 10 months
  • Last seen more than 9 years ago
31 votes

Open problems on the frontiers of TCS

28 votes
Accepted

Optimal algorithm for finding the girth of a sparse graph?

23 votes
Accepted

Complexity of Finding the Eigendecomposition of a Matrix

19 votes
Accepted

Does an algorithm exist to efficiently maintain connectedness information for a DAG in presence of inserts/deletes?

18 votes
Accepted

Shortest paths disallowing each edge

16 votes
Accepted

Complexity of computing the average distance of a graph

15 votes
Accepted

What is the name of this type of directed graph problem?

15 votes

Problems Between P and NPC

14 votes
Accepted

Parallel algorithms for directed st-connectivity

11 votes

Multiplicative version of 3-SUM

10 votes
Accepted

What bounds can be put on counting reachable nodes in a dag?

10 votes

Transitivity check vs. Transitive Closure

10 votes

What is the fastest deterministic algorithm for dynamic digraph reachability with no edge deletion?

9 votes

"Directed" problems that are easier than their "undirected" variant.

9 votes

Any algorithmic problem has a time complexity dominated by counting?

6 votes

All Pairs Shortest Path - Directed graph with integer weights

5 votes

Solving Superstring Exactly

5 votes

Route existence between n pairs of nodes

4 votes

Computing a transitive completion / path existence oracle