| Abstract |
The question we address in this paper is: Given an undirected graph that has Hamiltonian cycle, how long a path can one find in this graph, in polynomial time? B. Monien [7] first studied this problem and showed how to find paths of length Omega(log n/log log n). Karger Motwani and Ramkumar [6] then improved this to Omega(log n). Alon, Yuster and Zwick [2] further improved this and showed how to find paths of length c log n for any constant c in any graph that has such a path. Bazgan, Santha and Tuza [3] prove that the problem of finding a long path in even cubic Hamiltonian graphs is not constant approximable unless P = NP. In this paper we present an algorithm that finds paths of length Omega((log n/log log n)(2)) in Hamiltonian graphs. |
ICAR Research Data Repository for Knowledge Management