Record Details

An approximation algorithm for finding a long path in Hamiltonian graphs

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title An approximation algorithm for finding a long path in Hamiltonian graphs
 
Creator VISHWANATHAN, S
 
Description 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.
 
Publisher SIAM
 
Date 2011-10-27T00:52:17Z
2011-12-15T09:12:38Z
2011-10-27T00:52:17Z
2011-12-15T09:12:38Z
2000
 
Type Proceedings Paper
 
Identifier PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS,680-685
0-89871-453-2
http://dspace.library.iitb.ac.in/xmlui/handle/10054/16186
http://hdl.handle.net/100/2788
 
Source 11th Annual ACM/SIAM Symposium on Discrete Algorithms,SAN FRANCISCO, CA,JAN 09-11, 2000
 
Language English