The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs

The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs

0.00 Avg rating—0 Votes
Article ID: iaor19881139
Country: United States
Volume: 10
Issue: 2
Start Page Number: 187
End Page Number: 211
Publication Date: Jun 1989
Journal: Journal of Algorithms
Authors: ,
Keywords: networks, programming: travelling salesman
Abstract:

An algorithm is presented for finding a Hamiltonian cycle in 4-connected planar graphs. The algorithm uses linear time and storage space, while the previously best one given by Gouyou-Beauchamps uses O(n3) time and space, where n is the number of vertices in a graph.

Reviews

Required fields are marked *. Your email address will not be published.