The Complexity of Determining Existence a Hamiltonian Cycle is $O(n^3)$

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

The Hamiltonian cycle problem in digraph is mapped into a matching cover bipartite graph. Based on this mapping, it is proved that determining existence a Hamiltonian cycle in graph is $O(n^3)$.
6 papers

Keywords

Data Structures and Algorithms, Computational Complexity, Discrete Mathematics

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/131995

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0706.2725
 http://arxiv.org/abs/0706.2725

Collections

arXiv