A fast parallel algorithm for finding Hamiltonian cycles in dense graphs |
| |
Authors: | Gábor N Sárközy |
| |
Institution: | Computer Science Department, Worcester Polytechnic Institute, Worcester, MA 01609, USA Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, P.O. Box 63, Budapest, H-1518, Hungary |
| |
Abstract: | Suppose that 0<η<1 is given. We call a graph, G, on n vertices an η-Chvátal graph if its degree sequence d1≤d2≤?≤dn satisfies: for k<n/2, dk≤min{k+ηn,n/2} implies dn−k−ηn≥n−k. (Thus for η=0 we get the well-known Chvátal graphs.) An -algorithm is presented which accepts as input an η-Chvátal graph and produces a Hamiltonian cycle in G as an output. This is a significant improvement on the previous best -algorithm for the problem, which finds a Hamiltonian cycle only in Dirac graphs (δ(G)≥n/2 where δ(G) is the minimum degree in G). |
| |
Keywords: | Hamiltonian cycle Parallel algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|