Travelling Salesman
Reputation: 2271
Can we find a Hamiltonian Cycle in a dense graph with better than O(n^2)?
Given a dense graph (according to ore's theorem, dense means the sum of degrees of any 2 non-adjacent nodes is at least N, where N is the total number of nodes), we can find a Hamiltonian cycle in such a graph using Palmer's algorithm with a time complexity of O(n^2). My question is: Can we do better than this? (in terms of time complexity).
Upvotes: 2
Views: 332
Answers (0)
Related Questions
- Hamiltonian Cycle; Prove: if there's an efficient algorithm to determine that an HC exists, then there's an efficient FIND algorithm
- How to find Hamiltonian Cycle in a graph using BFS? (the condition is that the graph is exactly hamiltonian)
- Hamiltonian path generator algorithm
- How can I find the number of Hamiltonian cycles in a complete undirected graph?
- Find a Hamiltonian cycle of no more than twice the minimum cost in O(m+n log n) in an undirected graph with costs satisfying the triangle inequality
- How to find Hamiltonian Cycle in a Graph
- Divide Hamiltonian Cycle Optimally
- Fast Hamiltonian cycle calculation
- what whould be suitable algorithm?
- Checking if a Hamilton Cycle exists in a dense graph