User J. Schmidt

5 votes

2 answers

4k views

Why doesn't 2-opt return an optimal solution?

asked Apr 11, 2017 at 7:49

5 votes

1 answer

1k views

Can a graph problem remain NP-hard when restricted to cycle graphs?

asked Oct 9, 2023 at 17:01

4 votes

1 answer

600 views

Is there some kind of expected error margin for my Monte Carlo algorithm?

asked Nov 2, 2021 at 11:37

3 votes

1 answer

365 views

Approximation concerning Asymmetric TSP, Symmetric TSP, and Metric TSP

asked Sep 15, 2020 at 8:26

3 votes

1 answer

184 views

NP-hard $k$-SAT variant with exactly $\ell$ occurrences per variable

asked Oct 20, 2022 at 14:13

3 votes

1 answer

71 views

Basic second-order logic example contains a mistake?

asked Apr 23, 2019 at 13:45

3 votes

1 answer

125 views

Two questions on MSO

asked May 16, 2019 at 10:16

3 votes

3 answers

291 views

Is the P vs NP problem, an NP or co-NP problem?

asked Aug 13, 2019 at 21:09

3 votes

2 answers

826 views

Can non-metric TSP be approximated within some non-constant value?

asked Sep 24, 2019 at 13:50

3 votes

1 answer

55 views

graph theory single bar vs double bar size notation

asked Apr 3 at 13:48

2 votes

0 answers

55 views

Why can the construction of a polynomial-sized structure be done in logspace?

asked Feb 23, 2020 at 3:03

2 votes

0 answers

51 views

Bead-tiling algorithm for Dubins' TSP

asked Mar 6, 2017 at 15:45

2 votes

1 answer

97 views

What is the time complexity of removing among $N$ sets of size at most $n$ the sets which are subsets of another set?

asked Jan 12, 2023 at 17:32

2 votes

1 answer

42 views

What is the proper way to write logic formula, say concerning graph theory?

asked Feb 6, 2023 at 18:25

2 votes

1 answer

94 views

Intuitive proof that all planar graphs are disk contact graphs

asked Oct 21, 2021 at 14:10

1 vote

1 answer

53 views

Is the clique problem polynomial-time solvable still in unit disk graphs allowing different sized disks?

asked Oct 15, 2021 at 15:58

1 vote

0 answers

29 views

What knowledge do players $y_1$ and $y_2$ have exactly in this example for Dependency Quantified Boolean Formula?

asked Apr 18, 2022 at 18:39

1 vote

1 answer

53 views

Dubins TSP NP-hardness proof detail

asked Jul 13, 2019 at 11:11

1 vote

0 answers

28 views

Problem of making entities agree on some wavelength

asked Jul 22, 2019 at 8:47

1 vote

1 answer

48 views

Is deciding whether a graph admits two vertex-disjoint spanning trees of bounded size difference NP-hard?

asked Feb 9, 2023 at 17:50

1 vote

1 answer

163 views

Why does this algorithm not have an exponential complexity?

asked Mar 12, 2017 at 8:48

1 vote

2 answers

1k views

What is the graphic TSP?

asked Jun 14, 2019 at 13:41

1 vote

2 answers

73 views

Chordal graph question

asked May 9, 2019 at 12:36

1 vote

0 answers

76 views

How are metric TSP and Eulerian cycle equivalent? [closed]

asked Feb 23, 2020 at 5:29

1 vote

3 answers

289 views

Is this a Fixed Parameter Tractable algorithm?

asked Apr 11, 2020 at 13:16

1 vote

1 answer

48 views

Can PTAS be used to optimally solve Knapsack?

asked Jan 22 at 9:47

0 votes

2 answers

630 views

Can Dijkstra's algorithm outperform A star, in terms of vertices checked?

asked Sep 17, 2019 at 10:24

0 votes

2 answers

1k views

Coefficients in cost function in A-star

asked Sep 17, 2019 at 12:52

0 votes

1 answer

243 views

Grassfire vs BFS

asked Sep 17, 2019 at 13:31

0 votes

1 answer

46 views

Dubins TSP crossing trajectory theorem

asked Jul 8, 2019 at 10:12

Stack Exchange Network

39 Questions

Why doesn't 2-opt return an optimal solution?

Can a graph problem remain NP-hard when restricted to cycle graphs?

Is there some kind of expected error margin for my Monte Carlo algorithm?

Approximation concerning Asymmetric TSP, Symmetric TSP, and Metric TSP

NP-hard $k$-SAT variant with exactly $\ell$ occurrences per variable

Basic second-order logic example contains a mistake?

Two questions on MSO

Is the P vs NP problem, an NP or co-NP problem?

Can non-metric TSP be approximated within some non-constant value?

graph theory single bar vs double bar size notation

Why can the construction of a polynomial-sized structure be done in logspace?

Bead-tiling algorithm for Dubins' TSP

What is the time complexity of removing among $N$ sets of size at most $n$ the sets which are subsets of another set?

What is the proper way to write logic formula, say concerning graph theory?

Intuitive proof that all planar graphs are disk contact graphs

Is the clique problem polynomial-time solvable still in unit disk graphs allowing different sized disks?

What knowledge do players $y_1$ and $y_2$ have exactly in this example for Dependency Quantified Boolean Formula?

Dubins TSP NP-hardness proof detail

Problem of making entities agree on some wavelength

Is deciding whether a graph admits two vertex-disjoint spanning trees of bounded size difference NP-hard?

Why does this algorithm not have an exponential complexity?

What is the graphic TSP?

Chordal graph question

How are metric TSP and Eulerian cycle equivalent? [closed]

Is this a Fixed Parameter Tractable algorithm?

Can PTAS be used to optimally solve Knapsack?

Can Dijkstra's algorithm outperform A star, in terms of vertices checked?

Coefficients in cost function in A-star

Grassfire vs BFS

Dubins TSP crossing trajectory theorem