Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.

Sign up to join this community
Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top

Explore our Questions

0 votes
0 answers
6 views

Cheapest Insertion is $2$-approximation for TSP

0 votes
0 answers
38 views

Is Power Dominating Set in W[2]?

0 votes
0 answers
63 views

Does the Christofides algorithm ensure this inequality?

2 votes
1 answer
112 views

Is the center of a BFS tree a good approximation of the graphs center?

0 votes
0 answers
51 views

Parameterized Complexity of Vertex Multicut

1 vote
1 answer
91 views

Proving a property of minimal st-separators that are not minimum st-separators

4 votes
3 answers
2k views

Dynamic programming and shortest path problem

7 votes
2 answers
582 views

Capacitated multiple vehicle routing problem with handovers

17 votes
2 answers
4k views

Finding k shortest Paths with Eppstein's Algorithm

19 votes
2 answers
863 views

Axioms for Shortest Paths

1 vote
1 answer
139 views

Nontrivial Algorithms for Coloring (Parameterized by Pathwidth)

0 votes
0 answers
38 views

Reducing computing the partition function to computing the number of min-cardinality (s, t) cut

25 votes
5 answers
9k views

What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?

2 votes
1 answer
124 views

Parameterized algorithm when the parameter is not known in advance?

Browse more Questions