Skip to main content
Share Your Experience: Take the 2024 Developer Survey
Juho's user avatar
Juho's user avatar
Juho's user avatar
Juho
  • Member for 12 years, 2 months
  • Last seen this week
6 votes
1 answer
4k views

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

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?

14 votes
2 answers
1k views

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

15 votes
2 answers
1k views

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

20 votes
1 answer
957 views

Supporting data structures for SAT local search

16 votes
2 answers
896 views

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

8 votes
3 answers
694 views

What is the name of this logistic variant of TSP?

4 votes
1 answer
497 views

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

19 votes
1 answer
450 views

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

14 votes
1 answer
419 views

Research on evaluating the performance of cache-obliviousness in practice

6 votes
1 answer
400 views

Approximability of the edge-disjoint shortest paths problem

10 votes
1 answer
261 views

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

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)$?

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?