Skip to main content
Computer Science
pcpthm's user avatar
pcpthm's user avatar
pcpthm's user avatar
pcpthm
  • Member for 3 years, 10 months
  • Last seen this week
Profile Activity

76 Answers

Score Activity Newest
6 votes
Accepted

Vertex deletion algorithm with connected constraint

6 votes
Accepted

Improving a ranking system with "best rank"

6 votes
Accepted

Easy/hard NP-hard problems on perfect graphs

6 votes
Accepted

Prove that "max independent set is larger than max clique" is NP-Hard

5 votes
Accepted

Function which describes an optimal data structure for a bounded number of query operations?

5 votes
Accepted

Longest Repeated (Scattered) Subsequence in a String

5 votes
Accepted

Efficiently determine which nodes should leave a graph while maintaining connectedness

4 votes
Accepted

For $L_1 \in NP, L_2 \in NPC$, does $L_1 \in P \Rightarrow L_2 \in P$ imply $L_1 \in NPC$?

4 votes
Accepted

An intuitive explanation of "provably complex combinatorial games"

4 votes
Accepted

First-order model checking is not fixed parameter tractable on general graphs

4 votes

Can almost equal partition problem be solved in polynomial time?

4 votes

Algorithm for farthest point Voronoi diagram?

4 votes
Accepted

Optimal algorithmic complexity of "a nonrepetitive stack"?

4 votes
Accepted

Find the transitive closure but with a twist

3 votes
Accepted

Are Context-Free languages closed under XOR?

3 votes
Accepted

Is this graph grouping problem $\mathsf{NP}$-hard?

3 votes
Accepted

Minimize max subtree weight among spanning trees

3 votes
Accepted

Algorithm: Optimal selection of subset of nodes in undirected graph to minimize score

3 votes
Accepted

Choose non-adjacent numbers from intervals

3 votes
Accepted

Maximum distance between two points of a polyhedron

3 votes
Accepted

How many lower-case 6 letter words can I write so that every pair has exactly two matching letters?

3 votes

Why is finding the sign of the sum of exponentially real numbers in PP?

3 votes
Accepted

If $f \in \mathcal{o}(g)$, does $f \circ g \in \mathcal{o}(g \circ f)$?

3 votes

How to match two point sets to minimize total distance?

3 votes

How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

3 votes
Accepted

Applications of the DGIM algorithm

2 votes
Accepted

variant of assignment problem with overload penalties instead of constraints

2 votes
Accepted

Find every edge for which every s,t-path in a DAG goes through that edge

2 votes

Computing tr(ABCD...)

2 votes
Accepted

Efficient comparison, using only sum, product, difference, and conditional jump if zero

1
2 3