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
5 votes

Brzozowski's algorithm for DFA minimization

5 votes

Generalised 3SUM (k-SUM) problem?

5 votes

How fast can we find all Four-Square combinations that sum to N?

5 votes

In a CSP, what is an extensional constraint?

5 votes

Difference between heuristic and approximation algorithm?

5 votes
Accepted

Finding lambda of Master Theorem

5 votes
Accepted

What is the name of this logistic variant of TSP?

5 votes
Accepted

Shifting subset sum solution by constant positive integer

5 votes
Accepted

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

5 votes
Accepted

NP-completeness and NP problems

5 votes
Accepted

Is finding the longest path of a graph NP-complete?

5 votes

Is there any strategy to brute force search?

5 votes
Accepted

The equivalence relations cover problem (in graph theory)

5 votes

Discrete solution space in NP-complete problems

5 votes
Accepted

Finding the k-shortest path between two nodes

5 votes

Interesting small SAT problems?

5 votes
Accepted

Heuristic for weighted maximum independent set in graph with ~$2 \times 10^5$ nodes and $|E| \propto |V|$

5 votes

What is wrong with this reasoning that finding the genus of a degree 3 bipartite graph is NP-complete?

5 votes
Accepted

Is it true that independent set is $Ω(n^{1−\epsilon})$-inapproximable unless P=NP?

5 votes
Accepted

Vertex cover of a graph by removing leaf-vertices from a DFS tree

5 votes

Simple proof for NP-completeness of Edge Dominating Set

5 votes

Deterministic SAT solver

5 votes
Accepted

Connected components and graph edition

5 votes
Accepted

Finding all edges of an undirected graph which are in some cycle in linear time

5 votes

What does the $O^*$ notation mean?

5 votes
Accepted

NP-hard problems but only for n≥3

5 votes
Accepted

Has anyone seen a NP graph problem like this before?

5 votes
Accepted

maximum coverage version of dominating set

5 votes
Accepted

Minimize edges of a directed unweighted graph

5 votes
Accepted

Are there competitions for integer programming?

1 2 3
4
5
14