NP-Complete problems 2
Showcasing reductions between these NP-complete problems:
- 3SAT ≤p HCYCLE
- HCYCLE ≤p HCIRCUIT
- HCIRCUIT ≤p TSP
- 3SAT ≤p SSP
- 3SAT ≤p 3CG
Notes
- HCYCLE - "hamiltonovský cyklus", hamiltonian cycle in a directed graph
- HCIRCUIT - "hamiltonovská kruznice", hamiltonian cycle in an undirected graph