Skip to main content
Juho's user avatar
Juho's user avatar
Juho's user avatar
Juho
  • Member for 12 years, 3 months
  • Last seen this week
20 votes
1 answer
957 views

Supporting data structures for SAT local search

19 votes
1 answer
450 views

Problems for which algorithms based on partition refinement run faster than in loglinear time

16 votes
2 answers
900 views

Runtime of the optimal greedy $2$-approximation algorithm for the $k$-clustering problem

15 votes
2 answers
1k views

Decision problems in $\mathsf{P}$ without fast algorithms

14 votes
1 answer
420 views

Research on evaluating the performance of cache-obliviousness in practice

14 votes
2 answers
1k views

Efficiently sampling shortest $s$-$t$ paths uniformly and independently at random

10 votes
1 answer
261 views

Given a chordal graph $G$, what is the complexity of computing the reduced clique graph $C_r(G)$?

8 votes
3 answers
695 views

What is the name of this logistic variant of TSP?

7 votes
2 answers
2k views

3-SAT where variables occur equally many times as a positive literal and as a negative literal

6 votes
2 answers
2k views

Is the $k$P$k$N-3SAT problem NP-complete?

6 votes
1 answer
4k views

What is the maximum number of shortest paths between any pair of vertices in a chordal graph?

6 votes
1 answer
400 views

Approximability of the edge-disjoint shortest paths problem

6 votes
1 answer
216 views

What's a fast algorithm to decide whether there is an $A_G$ corresponding to a given $\chi_G(\lambda)$?

4 votes
1 answer
498 views

Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space

3 votes
1 answer
179 views

How to quickly find a few bisimulations on a given labelled digraph?

2 votes
1 answer
100 views

What is a good resource to learn about oriented matroids in the context of digraphs and optimization?