Nathan
Reputation: 1
Is the complexity of the seating problem equal to a similar Hamiltonian circuit (cycle)?
You would have to convert an instance of the seating problem to an instance of Hamiltonian circuit (cycle). Does this mean in terms of complexity if one takes a certain complexity it cannot be guaranteed that the respective other could be completed in the same complexity?
Upvotes: 0
Views: 106
Answers (0)
Related Questions
- Dynamic Programming: Number of Seating Arrangements
- Hamiltonian Cycle; Prove: if there's an efficient algorithm to determine that an HC exists, then there's an efficient FIND algorithm
- Hamiltonian Path vs Shortest Path
- Hamiltonian path generator algorithm
- Hamiltonian Path Algorithm Time-Complexity
- Finding Hamiltonian path vs Hamiltonian circuit in a complete undirected weighted graph
- Complete Weighted Graph and Hamiltonian Tour
- Optimal Seating Arrangement Algorithm
- GCJ - Hamiltonian Cycles
- Divide Hamiltonian Cycle Optimally