Inuyasha Yagami's user avatar
Inuyasha Yagami's user avatar
Inuyasha Yagami's user avatar
Inuyasha Yagami
  • Member for 4 years, 4 months
  • Last seen this week
27 votes
Accepted

Is there a known polynomial time complexity problem with bad constants?

9 votes

False proofs that look correct

9 votes

False proofs that look correct

8 votes

False proofs that look correct

6 votes

Why is my implementation of Dijkstra's Algorithm using min heap faster than using an unsorted array for a complete graph?

5 votes

How does Dijkstra's problem 1 (tree of minimal total length) work and what does it do?

5 votes
Accepted

Let the vertices of the graph G be the numbers 1, 2, ..., 100, a. Determine χ(G), the chromatic number of the graph G

4 votes

What is the time complexity of this algorithm of finding all prime numbers?

4 votes
Accepted

Number of "one neighbourhood" search trees in a graph

4 votes
Accepted

What is a guarenteed amount of colors, depending on the graph's arboricity

4 votes

0/1 knapsack problem: Greedy Algorithm Counterexample

4 votes

Minimum number of groups such that every element in graph is included?

4 votes
Accepted

Minimum set cover with incompatible sets

4 votes
Accepted

What is the difference between Euler and Eulerian graph?

4 votes

Solve $T (n) = T (\frac n2) + n(2 - \cos n)$

4 votes
Accepted

Parition a multiset of numbers into two subsets, how to maximize the sum of their medians?

3 votes

Partitioning a graph into connected pairs and triplets

3 votes

Convex Polygon Triangulation: Line Intersects at most $O(\log n)$ Triangles

3 votes

A function which is both $o(\log^* n)$ and $\omega(1)$

3 votes
Accepted

Maximum independent subset for graphs with lots of edges

3 votes

Find a minimum-cardinality Hall-violator

3 votes
Accepted

Complexity of a variant of Subset Sum problem

3 votes

Minimum time to finish all meetings

3 votes

Can you use Dijkstra's algorithm to find the maximum cost path?

3 votes

What is the optimal solution for the following "Largest lexicographical string with <= K consecutive elements" problem? Why is my answer wrong?

3 votes
Accepted

Check array in linear time with a constant space complexity

3 votes
Accepted

Each cycle in the graph, the edge with the minimum weight belongs to MST

3 votes
Accepted

Graph with $\Theta(2^n)$ minimum $(s, t)$-cuts

3 votes

Approximation of Set Cover

3 votes

Isn't linear time O(n)?

1
2 3 4 5
7